Here are two solutions to problem D of today's contest
1.First solution
My Code
#include <bits/stdc++.h>
using namespace std;
void init_code(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
}
int main() {
init_code();
// read(T);
int T;
cin>>T;
while(T--){
int n,ans = 0;
cin>>n;
vector<string>v(n);
for(auto&i:v){
cin>>i;
}
vector<vector<int>>left(n,vector<int>(n)), right(n,vector<int>(n)), down(n, vector<int>(n));
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
int x = v[i][j] - '0';
if(left[i][j]){
x^=1;
if(i + 1 < n){
if(j - 1>=0){
left[i + 1][j - 1]^=1;
}
down[i + 1][j]^=1;
}
}
if(down[i][j]){
x^=1;
if(i + 1 <n){
down[i + 1][j]^=1;
}
}
if(right[i][j]){
x^=1;
if(i + 1 < n){
if(j + 1 < n){
right[i + 1][j + 1]^=1;
}
down[i + 1][j]^=1;
}
}
if(x){
ans++;
if(i + 1 < n){
if(j - 1 >= 0){
left[i + 1][j - 1]^=1;
}
if(j + 1<n){
right[i + 1][j + 1]^=1;
}
down[i + 1][j]^=1;
}
}
}
}
cout<<ans<<endl;
}
}
- Second solution
His Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 998244353;
template <typename T>
istream &operator>>(istream &istream, vector<T> &v){for (auto &it : v) cin >> it; return istream;}
template <typename T>
ostream &operator<<(ostream &ostream, vector<T> &v){for (auto &it : v) cout << it << ' '; return ostream;}
void solveIt(){
int n; cin >> n;
vector<string> a(n);
for(auto &i : a) cin >> i;
vector<vector<int>> left(n,vector<int> (n,0)),right(n,vector<int> (n,0)),down(n,vector<int> (n,0));
int ans = 0;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int x = a[i][j] - '0';
if(left[i][j]){
x ^= 1;
if(i + 1 < n){
if(j - 1 >= 0) left[i + 1][j - 1] ^= 1;
down[i + 1][j] ^= 1;
}
}
if(down[i][j]){
x ^= 1;
if(i + 1 < n) down[i + 1][j] ^= 1;
}
if(right[i][j]){
x ^= 1;
if(i + 1 < n){
if(j + 1 < n) right[i + 1][j + 1] ^= 1;
down[i + 1][j] ^= 1;
}
}
if(x){
ans++;
if(i + 1 < n){
if(j - 1 >= 0) left[i + 1][j - 1] ^= 1;
down[i + 1][j] ^= 1;
if(j + 1 < n) right[i + 1][j + 1] ^= 1;
}
}
}
}
cout << ans << '\n';
}
#undef int
int main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int tcs=1;
cin >> tcs;
for(int i=1;i<=tcs;i++){
solveIt();
}
}
The first one shows TLE on testcase 8 while the second one shows accepted. Both are same solutions to the problem.
Does anyone know why the results are so different?
Auto comment: topic has been updated by FullMetalChains (previous revision, new revision, compare).
Fast IO
Add this line to the beginning of your code and it will pass the tests:
Normally,
cinis "tied" tocout. This means that every timecinis used to read input,coutflushes its buffer. Normally,coutstores the outputted stuff in a buffer and only flushes it (prints it to stdout) once the program finishes. But usingcinmakescoutflush during the run of the program. Flushing is slow, not flushing is fast.cin.tie(0)disables this flushing ofcoutwhen usingcin.Normally, the IO methods from C (
scanf/printf) are synced with the C++ IO methods (cin/cout). This synchronization is slow. If you only use one of these (i.e. onlyscanfandprintfor onlycinandcout), you don't need this synchronization. Callingsync_with_stdio(0)disables this, making IO even faster.P.S. You might also sometimes see it written as
or something similar. That is identical to the line of code I mentioned.
This is so unfortunate. I resubmitted the answer I had during the contest(It gave TLE at that time) and now, it passed now. I feel robbed :(
I also noticed that FullMetalChains uses endl in submissions. For a similar reason, you should try using '\n' instead for non-interactive problems so it avoids flushing.
I always add
#define endl '\n', I find it easier to just comment it out on interactive problems. (If you are used to writingendllike me, you might consider doing this as well)Auto comment: topic has been updated by FullMetalChains (previous revision, new revision, compare).