Codeforces Round #373 Div. 2 review

Updated on September 26, 2016 by corochann · Leave a comment

Link Codeforces Round #373 Div. 2 (Contest 719) A. Vitya in the Countryside Problem Basically, check last 2 character to determine its direction is “UP” or “DOWN”. Special case comes when the last number is 0 or 15, in that case the direction changes and you can determine the direction without looking second last character.

#include <cstdio>
#include <iostream>

using namespace std;

int a[100];

int main(){
#ifndef ONLINE_JUDGE
    freopen("a3.in", "r", stdin);
#endif
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d", &a[i]);
    }
    if (n >= 2) {
        if (a[n-1] == 15) {
            printf("DOWN\n");
        } else if (a[n-1] == 0) {
            printf("UP\n");
        } else {
            if (a[n-1] > a[n-2]) {
                printf("UP\n");
            } else {
                printf("DOWN\n");
            }
        }
    } else if (n == 1) {
        if (a[n-1] == 15) {
            printf("DOWN\n");
        } else if (a[n-1] == 0) {
            printf("UP\n");
        } else {
            printf("-1\n");
        }
    }
    return 0;
}

#include <cstdio>

#include <iostream>

using namespace std;

int a[100];

int main(){

#ifndef ONLINE_JUDGE

freopen("a3.in", "r", stdin);

#endif

int n;

scanf("%d", &n);

for (int i = 0; i < n; ++i) {

scanf("%d", &a[i]);

}

if (n >= 2) {

if (a[n-1] == 15) {

printf("DOWN\n");

} else if (a[n-1] == 0) {

printf("UP\n");

} else {

if (a[n-1] > a[n-2]) {

printf("UP\n");

} else {

printf("DOWN\n");

}

} else if (n == 1) {

if (a[n-1] == 15) {

printf("DOWN\n");

} else if (a[n-1] == 0) {

printf("UP\n");

} else {

printf("-1\n");

}

return 0;

}

B. Anatoly […]

Continue reading →

Codeforces Round #368 Div. 2 review

Updated on September 2, 2016 by corochann · Leave a comment

Link Codeforces Round #368 Div. 2 (Contest 707) A. Brain’s Photos Problem Just need to check if color (Cyan, Magenta or Yellow) exists or not in the photo.

#include <cstdio>
#include <iostream>

using namespace std;

int main(){
#ifndef ONLINE_JUDGE
    freopen("a3.in", "r", stdin);
#endif
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            char c;
            cin >> c;
            if (c == 'C' || c == 'M' || c == 'Y') {
                cout << "#Color" << endl;
                return 0;
            }
        }
    }
    cout << "#Black&White" << endl;
    return 0;
}

#include <cstdio>

#include <iostream>

using namespace std;

int main(){

#ifndef ONLINE_JUDGE

freopen("a3.in", "r", stdin);

#endif

int n, m;

cin >> n >> m;

for (int i = 0; i < n; ++i) {

for (int j = 0; j < m; ++j) {

char c;

cin >> c;

if (c == 'C' || c == 'M' || c == 'Y') {

cout << "#Color" << endl;

return 0;

}

cout << "#Black&White" << endl;

return 0;

}

B. Bakery Problem The problem sentence looks long, but after summarize, you just need to find the path between flour storage city and non flour […]

Continue reading →

scanf and printf are much faster than cin and cout

Updated on September 2, 2016 by corochann · 1 Comment

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;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

* 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;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

* 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;

}

[…]

Continue reading →

corochannNote

Month: September 2016

Codeforces Round #373 Div. 2 review

Codeforces Round #368 Div. 2 review

scanf and printf are much faster than cin and cout