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,
cin
is "tied" tocout
. This means that every timecin
is used to read input,cout
flushes its buffer. Normally,cout
stores the outputted stuff in a buffer and only flushes it (prints it to stdout) once the program finishes. But usingcin
makescout
flush during the run of the program. Flushing is slow, not flushing is fast.cin.tie(0)
disables this flushing ofcout
when 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. onlyscanf
andprintf
or onlycin
andcout
), 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 writingendl
like me, you might consider doing this as well)Auto comment: topic has been updated by FullMetalChains (previous revision, new revision, compare).