oj.uz

답안 #415608

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
415608 2021-06-01T09:38:31 Z qwerasdfzxcl Vision Program (IOI19_vision) C++14
10 / 100
 10 ms 1352 KB 
#include <bits/stdc++.h>
#include "vision.h"

typedef long long ll;
using namespace std;
vector<int> p;
int factor[202];
bool prime[202];

void getprime(){
    fill(prime+2, prime+202, 1);
    for (int i=2;i<202;i++) if (prime[i]){
        p.push_back(i);
        for (int j=2;i*j<202;j++) prime[i*j] = 1;
    }
}

void factorize(int n){
    fill(factor, factor+202, 0);
    for (auto &x:p){
        while(n%x==0){
            factor[x]++;
            n /= x;
        }
    }
}

void construct_network(int n, int m, int k) {
    getprime();
    vector<int> row;
    for (int i=0;i<n;i++){
        vector<int> tmp;
        for (int j=0;j<m;j++) tmp.push_back(i*m+j);
        row.push_back(add_or(tmp));
    }
    int row_pos0 = add_xor(row);
    vector<vector<int>> row_pk;
    row_pk.resize(n);
    for (int i=0;i<n;i++){
        row_pk[i].push_back(-1);
        if (!prime[i]) continue;
        for (int cur=i;cur<n;cur*=i){
            vector<int> tmp2;
            for (int t=0;t<cur;t++){
                vector<int> tmp;
                for (int j=0;t+i*j<n;j++) tmp.push_back(row[t+i*j]);
                if (tmp.size()==1){
                    tmp2.push_back(tmp[0]);
                    continue;
                }
                tmp2.push_back(add_xor(tmp));
            }
            row_pk[i].push_back(add_not(add_or(tmp2)));
            add_not(row_pk[i].back());
        }
    }
    row_pk[0][0] = row_pos0;
    vector<int> tmpv_row;
    tmpv_row.push_back(row_pos0);
    for (int i=2;i<n;i++){
        factorize(i);
        vector<int> tmp;
        for (auto &x:p){
            if (x>=n) break;
            if (factor[x]) tmp.push_back(row_pk[x][factor[x]]);
            if (factor[x]<(int)row_pk[x].size()-1) tmp.push_back(row_pk[x][factor[x]+1]+1);
        }
        row_pk[i][0] = add_and(tmp);
        tmpv_row.push_back(row_pk[i][0]);
    }
    if (n>1) row_pk[1][0] = add_not(add_or(tmpv_row));



    vector<int> col;
    for (int j=0;j<m;j++){
        vector<int> tmp;
        for (int i=0;i<n;i++) tmp.push_back(i*m+j);
        col.push_back(add_or(tmp));
    }
    int col_pos0 = add_xor(col);
    vector<vector<int>> col_pk;
    col_pk.resize(m);
    for (int j=0;j<m;j++){
        col_pk[j].push_back(-1);
        if (!prime[j]) continue;
        for (int cur=j;cur<m;cur*=j){
            vector<int> tmp2;
            for (int t=0;t<cur;t++){
                vector<int> tmp;
                for (int i=0;t+i*j<m;i++) tmp.push_back(col[t+i*j]);
                if (tmp.size()==1){
                    tmp2.push_back(tmp[0]);
                    continue;
                }
                tmp2.push_back(add_xor(tmp));
            }
            col_pk[j].push_back(add_not(add_or(tmp2)));
            add_not(col_pk[j].back());
        }
    }
    col_pk[0][0] = col_pos0;
    vector<int> tmpv_col;
    tmpv_col.push_back(col_pos0);
    for (int j=2;j<m;j++){
        factorize(j);
        vector<int> tmp;
        for (auto &x:p){
            if (x>=m) break;
            if (factor[x]) tmp.push_back(col_pk[x][factor[x]]);
            if (factor[x]<(int)col_pk[x].size()-1) tmp.push_back(col_pk[x][factor[x]+1]+1);
        }
        col_pk[j][0] = add_and(tmp);
        tmpv_col.push_back(col_pk[j][0]);
    }
    if (m>1) col_pk[1][0] = add_not(add_or(tmpv_col));

    vector<int> ans;
    for (int i=0;i<=k;i++){
        if (i>=n || k-i>=m) continue;
        vector<int> tmp;
        tmp.push_back(row_pk[i][0]);
        tmp.push_back(col_pk[k-i][0]);
        ans.push_back(add_and(tmp));
    }
    add_or(ans);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 296 KB on inputs (0, 2), (0, 4), expected 1, but computed 0
22 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 296 KB on inputs (0, 2), (0, 4), expected 1, but computed 0
22 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 296 KB on inputs (0, 2), (0, 4), expected 1, but computed 0
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1224 KB WA in grader: Too many instructions
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 10 ms 932 KB on inputs (0, 0), (100, 0), expected 0, but computed 1
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 1352 KB WA in grader: Too many instructions
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1 ms 204 KB Output is correct
13 Correct 1 ms 292 KB Output is correct
14 Correct 1 ms 292 KB Output is correct
15 Correct 1 ms 204 KB Output is correct
16 Correct 1 ms 204 KB Output is correct
17 Correct 1 ms 204 KB Output is correct
18 Correct 1 ms 204 KB Output is correct
19 Correct 1 ms 204 KB Output is correct
20 Correct 1 ms 204 KB Output is correct
21 Incorrect 1 ms 296 KB on inputs (0, 2), (0, 4), expected 1, but computed 0
22 Halted 0 ms 0 KB -