oj.uz

Submission #269261

# Submission time Handle Problem Language Result Execution time Memory
269261 2020-08-17T05:58:21 Z 반딧불(#5114) Chameleon's Love (JOI20_chameleon) C++17
40 / 100
 38 ms 404 KB 
#include <bits/stdc++.h>
#include "chameleon.h"

using namespace std;

int n;
vector<int> link[1002];
int opp[1002];

vector<int> range(int l, int r){
    vector<int> ret;
    for(int i=l; i<=r; i++) ret.push_back(i);
    return ret;
}

int group[1002];
int fast[1002];
vector<int> groupVec[3];

void dfs(int x, int g){
    group[x] = g;
    groupVec[g].push_back(x);
    for(auto &y: link[x]){
        if(!group[y]) dfs(y, 3-g);
    }
}

void Solve(int N){
    n = N;
    for(int i=1; i<=2*n; i++){
        for(int j=1; j<=2*n; j++){
            if(i==j) continue;
            if(Query({i, j}) == 1) link[i].push_back(j);
        }
    }

    for(int i=1; i<=2*n; i++){
        if(!group[i]){
            dfs(i, 1);
        }
    }
    for(int i=1; i<=2*n; i++){
        if((int)link[i].size() == 1){
            opp[i] = link[i][0];
            fast[i] = 1;
        }
    }

    for(int i=1; i<=2*n; i++){
        if((int)link[i].size() == 1){
            continue;
        }

        int g1 = link[i][0], g2 = link[i][1], g3 = link[i][2];
        opp[i] += g1 + g2 + g3;
        int q1 = Query({i, g2, g3}), q2 = Query({i, g1, g3});
        if(q1 == 1){
            opp[i] -= g1;
            if(!fast[g1]) opp[g1] -= i;
        }
        else if(q2 == 1){
            opp[i] -= g2;
            if(!fast[g2]) opp[g2] -= i;
        }
        else{
            opp[i] -= g3;
            if(!fast[g3]) opp[g3] -= i;
        }
    }

    for(int i=1; i<=2*n; i++){
        if(i < opp[i]) Answer(i, opp[i]);
    }
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 29 ms 404 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 324 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 4 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 3 ms 384 KB Output is correct
13 Correct 3 ms 384 KB Output is correct
14 Correct 6 ms 384 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 5 ms 384 KB Output is correct
18 Correct 5 ms 384 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Incorrect 38 ms 384 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 29 ms 404 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -