scanf and printf are much faster than cin and cout

When I’m solving the Codeforces problem, 707D. Persistent Bookcase, I made some comparison for the performance of I/O function.

  • scanf() and printf()
  • cin >> and cout <<

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

functiontime
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!

Leave a Comment

Your email address will not be published. Required fields are marked *