oj.uz

답안 #73203

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
73203 2018-08-28T04:34:39 Z test 재채점 전쟁 (FXCUP3_judge) C++14
49 / 100
 1500 ms 172124 KB 
#include<bits/stdc++.h>
using namespace std;

const int MN = 500010;

int X, D, C;
int data[MN], code[MN], cnt1[1 << 20], cnt2[1 << 20];

int cc1[1 << 20][20];
int dp1(int mask, int p) {
    if(p == X) return cnt1[mask]? mask : 0;
    int &ret = cc1[mask][p];
    if(ret != -1) return ret;

    ret = 0;
    if(mask & (1 << p)) {
        ret |= dp1(mask, p + 1);
        ret |= dp1(mask ^ (1 << p), p + 1);
    }
    else ret |= dp1(mask, p + 1);
    return ret;
}

int cc2[1 << 20][20];
int dp2(int mask, int p) {
    if(p == X) return cnt2[mask];
    int &ret = cc2[mask][p];
    if(ret != -1) return ret;

    ret = 0;
    if(mask & (1 << p)) {
        ret += dp2(mask, p + 1);
        ret += dp2(mask ^ (1 << p), p + 1);
    }
    else ret += dp2(mask, p + 1);
    return ret;
}

int ans[MN];

int main() {
    scanf("%d", &X);
    scanf("%d", &D);

    for(int i = 0; i < D; i++) {
        scanf("\n");
        for(int j = 0; j < X; j++) {
            char t; scanf("%c", &t);

            if(t == 'o') data[i] ^= (1 << j);
        }
        cnt1[ data[i] ]++;
    }

    scanf("%d", &C);

    for(int i = 0; i < C; i++) {
        scanf("\n");
        for(int j = 0; j < X; j++) {
            char t; scanf("%c", &t);

            if(t == 'x') code[i] ^= (1 << j);
        }
        cnt2[ code[i] ]++;
    }

    memset(cc1, -1, sizeof(cc1));
    memset(cc2, -1, sizeof(cc2));

    for(int i = 0; i < (1 << X); i++) {
        if(dp1(i, 0) == i) {
            ans[ C - dp2((1 << X) - 1 - i, 0) ] = 1;
        }
    }
    for(int i = 1; i <= C; i++) {
        if(ans[i]) printf("o");
        else printf("x");
    }
}

Compilation message

judge.cpp: In function 'int main()':
judge.cpp:42:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &X);
     ~~~~~^~~~~~~~~~
judge.cpp:43:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &D);
     ~~~~~^~~~~~~~~~
judge.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
judge.cpp:48:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             char t; scanf("%c", &t);
                     ~~~~~^~~~~~~~~~
judge.cpp:55:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &C);
     ~~~~~^~~~~~~~~~
judge.cpp:58:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n");
         ~~~~~^~~~~~
judge.cpp:60:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             char t; scanf("%c", &t);
                     ~~~~~^~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 164608 KB Output is correct
2 Correct 146 ms 164608 KB Output is correct
3 Correct 148 ms 164636 KB Output is correct
4 Correct 153 ms 164676 KB Output is correct
5 Correct 147 ms 164752 KB Output is correct
6 Correct 150 ms 164756 KB Output is correct
7 Correct 151 ms 164756 KB Output is correct
8 Correct 155 ms 164756 KB Output is correct
9 Correct 157 ms 164972 KB Output is correct

Subtask #2
39.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 164608 KB Output is correct
2 Correct 146 ms 164608 KB Output is correct
3 Correct 148 ms 164636 KB Output is correct
4 Correct 153 ms 164676 KB Output is correct
5 Correct 147 ms 164752 KB Output is correct
6 Correct 150 ms 164756 KB Output is correct
7 Correct 151 ms 164756 KB Output is correct
8 Correct 155 ms 164756 KB Output is correct
9 Correct 157 ms 164972 KB Output is correct
10 Correct 674 ms 167284 KB Output is correct
11 Correct 410 ms 167284 KB Output is correct
12 Correct 195 ms 167284 KB Output is correct
13 Correct 145 ms 167284 KB Output is correct
14 Correct 602 ms 167284 KB Output is correct
15 Correct 700 ms 167632 KB Output is correct
16 Correct 1199 ms 169516 KB Output is correct
17 Correct 1220 ms 169772 KB Output is correct

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 144 ms 164608 KB Output is correct
2 Correct 146 ms 164608 KB Output is correct
3 Correct 148 ms 164636 KB Output is correct
4 Correct 153 ms 164676 KB Output is correct
5 Correct 147 ms 164752 KB Output is correct
6 Correct 150 ms 164756 KB Output is correct
7 Correct 151 ms 164756 KB Output is correct
8 Correct 155 ms 164756 KB Output is correct
9 Correct 157 ms 164972 KB Output is correct
10 Correct 674 ms 167284 KB Output is correct
11 Correct 410 ms 167284 KB Output is correct
12 Correct 195 ms 167284 KB Output is correct
13 Correct 145 ms 167284 KB Output is correct
14 Correct 602 ms 167284 KB Output is correct
15 Correct 700 ms 167632 KB Output is correct
16 Correct 1199 ms 169516 KB Output is correct
17 Correct 1220 ms 169772 KB Output is correct
18 Correct 1055 ms 169772 KB Output is correct
19 Correct 908 ms 169772 KB Output is correct
20 Execution timed out 1573 ms 172124 KB Time limit exceeded
21 Halted 0 ms 0 KB -