When I’m solving the Codeforces problem, 707D. Persistent Bookcase, I made some comparison for the performance of I/O function.
scanf()andprintf()cin >>andcout <<
Test
Let’s start from C++ common way, below code uses cin >> and cout <<
/*
* Ref: http://codeforces.com/submissions/ksun48 707D
* Use DFS
* forward & backward
*
* Accepted 748 ms 11500 KB
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n, m;
int a[100005], b[100005], c[100005];
int ans[100005];
bool shelf[1005][1005];
int count_shelf[1005];
int total_count = 0;
vector<int> children[100005]; // children[i] : child of i-th operation = next operation
void dfs(int q) { // now at q-th operation
ans[q] = total_count;
//cout << "debug q = " << q << ", ans[q] = " << ans[q] << endl;
for (int i = 0; i < children[q].size(); ++i) {
int curq = children[q][i];
/* Forward, Apply q-th operation */
bool changed = false;
switch (a[curq]) {
case 1:
if (!shelf[b[curq]][c[curq]]) {
count_shelf[b[curq]]++;
total_count++;
shelf[b[curq]][c[curq]] = true;
changed = true;
}
break;
case 2:
if (shelf[b[curq]][c[curq]]) {
count_shelf[b[curq]]--;
total_count--;
shelf[b[curq]][c[curq]] = false;
changed = true;
}
break;
case 3:
for (int j = 0; j < m; ++j) {
shelf[b[curq]][j] = !shelf[b[curq]][j];
}
total_count += m - 2 * count_shelf[b[curq]];
count_shelf[b[curq]] = m - count_shelf[b[curq]];
break;
case 4:
// jumped from q to curq, do nothing
break;
}
dfs(curq);
/* Backward Rollback q-th operation.
* changed flag, set at forward operation, is used. */
switch (a[curq]) {
case 1:
if (changed) {
count_shelf[b[curq]]--;
total_count--;
shelf[b[curq]][c[curq]] = false;
}
break;
case 2:
if (changed) {
count_shelf[b[curq]]++;
total_count++;
shelf[b[curq]][c[curq]] = true;
}
break;
case 3:
for (int j = 0; j < m; ++j) {
shelf[b[curq]][j] = !shelf[b[curq]][j];
}
total_count += m - 2 * count_shelf[b[curq]];
count_shelf[b[curq]] = m - count_shelf[b[curq]];
break;
case 4:
// do nothing and go back from curq to q
break;
}
//cout << "debug after rollback q = " << q << ", ans[q] = " << ans[q] << endl;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("d4.in", "r", stdin);
#endif
//vector<int> v;
int q;
cin >> n >> m >> q;
for (int i = 1; i <= q; ++i) {
cin >> a[i];
if (a[i]==1 || a[i]==2) {
cin >> b[i] >> c[i];
b[i]--;
c[i]--;
} else {
cin >> b[i];
if (a[i]==3) {
b[i]--;
}
}
/* Create DFS tree */
if (a[i]==4) {
// i-th operation is 4
children[b[i]].push_back(i);
} else {
children[i-1].push_back(i);
}
}
dfs(0);
for (int i = 1; i <= q; ++i) {
cout << ans[i] << endl;
}
return 0;
}
It took 748 ms.
Next, (old-school,) C way of implementation using scanf() and printf()
/*
* Ref: http://codeforces.com/submissions/ksun48 707D
* Use DFS
* forward & backward
*
* Use scanf, printf instead of cin, cout
* scanf & printf: 171 ms 11500 KB --> The difference is super huge. Use scanf & printf.
*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
int n, m;
int a[100005], b[100005], c[100005];
int ans[100005];
bool shelf[1005][1005];
int count_shelf[1005];
int total_count = 0;
vector<int> children[100005]; // children[i] : child of i-th operation = next operation
void dfs(int q) { // now at q-th operation
ans[q] = total_count;
//cout << "debug q = " << q << ", ans[q] = " << ans[q] << endl;
for (int i = 0; i < children[q].size(); ++i) {
int curq = children[q][i];
/* Forward, Apply q-th operation */
bool changed = false;
switch (a[curq]) {
case 1:
if (!shelf[b[curq]][c[curq]]) {
count_shelf[b[curq]]++;
total_count++;
shelf[b[curq]][c[curq]] = true;
changed = true;
}
break;
case 2:
if (shelf[b[curq]][c[curq]]) {
count_shelf[b[curq]]--;
total_count--;
shelf[b[curq]][c[curq]] = false;
changed = true;
}
break;
case 3:
for (int j = 0; j < m; ++j) {
shelf[b[curq]][j] = !shelf[b[curq]][j];
}
total_count += m - 2 * count_shelf[b[curq]];
count_shelf[b[curq]] = m - count_shelf[b[curq]];
break;
case 4:
// jumped from q to curq, do nothing
break;
}
dfs(curq);
/* Backward Rollback q-th operation.
* changed flag, set at forward operation, is used. */
switch (a[curq]) {
case 1:
if (changed) {
count_shelf[b[curq]]--;
total_count--;
shelf[b[curq]][c[curq]] = false;
}
break;
case 2:
if (changed) {
count_shelf[b[curq]]++;
total_count++;
shelf[b[curq]][c[curq]] = true;
}
break;
case 3:
for (int j = 0; j < m; ++j) {
shelf[b[curq]][j] = !shelf[b[curq]][j];
}
total_count += m - 2 * count_shelf[b[curq]];
count_shelf[b[curq]] = m - count_shelf[b[curq]];
break;
case 4:
// do nothing and go back from curq to q
break;
}
//cout << "debug after rollback q = " << q << ", ans[q] = " << ans[q] << endl;
}
}
int main(){
#ifndef ONLINE_JUDGE
freopen("d4.in", "r", stdin);
#endif
//vector<int> v;
int q;
scanf("%d %d %d", &n, &m, &q);
for (int i = 1; i <= q; ++i) {
scanf("%d", &a[i]);
if (a[i]==1 || a[i]==2) {
scanf("%d %d", &b[i], &c[i]);
b[i]--;
c[i]--;
} else {
scanf("%d", &b[i]);
if (a[i]==3) {
b[i]--;
}
}
/* Create DFS tree */
if (a[i]==4) {
// i-th operation is 4
children[b[i]].push_back(i);
} else {
children[i-1].push_back(i);
}
}
dfs(0);
for (int i = 1; i <= q; ++i) {
printf("%d\n", ans[i]);
//cout << ans[i] << endl;
}
return 0;
}
It took only 171 ms.
Result
| function | time |
scanf() and printf() | 171 ms |
cin >> and cout << | 748 ms |
In this experiment, it appears that the speed of cin and cout is much much slower than scanf() and printf(), the difference is indeed quite huge.
The overhead of cin and cout took more than 500 ms! You might get a TLE using cin and cout while it is not necessary with scanf() and printf().
Conclusion: Use scanf and printf instead of cin and cout in programming contest!