oj.uz

Submission #269349

# Submission time Handle Problem Language Result Execution time Memory
269349 2020-08-17T06:37:54 Z 반딧불(#5114) Chameleon's Love (JOI20_chameleon) C++17
44 / 100
 48 ms 512 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;
    if(link[x].size() <= 2) 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=2; i<=2*n; i++){
        memset(group, 0, sizeof(group));
        groupVec[1].clear(), groupVec[2].clear();
        for(int j=1; j<i; j++){
            if(!group[j]) dfs(j, (groupVec[1].size() < groupVec[2].size()) ? 1 : 2);
        }

        int cnt=0;
        for(int session = 1; session <= 2; session ++){
            int l = 0, r = (int)groupVec[session].size()-1, nxt = (int)groupVec[session].size();
            while(1){
                if(cnt >= 3) break;
                while(l<=r){
                    int m = (l+r+1)>>1;
                    vector<int> queryVec (groupVec[session].begin()+l, groupVec[session].begin()+m+1);
                    queryVec.push_back(i);
                    int qq = Query(queryVec);

                    if(qq != (int)queryVec.size()) nxt = m, r = m-1;
                    else l = m+1;
                }

                if(nxt == (int)groupVec[session].size()) break;
                int tmp = groupVec[session][nxt];
//                printf("%d - %d\n", i, tmp);
                link[i].push_back(tmp), link[tmp].push_back(i);
                l = nxt+1, r = (int)groupVec[session].size()-1, nxt = r+1;
                cnt++;
            }
        }
    }

    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
4.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 Correct 40 ms 384 KB Output is correct
4 Correct 40 ms 384 KB Output is correct
5 Correct 40 ms 384 KB Output is correct
6 Correct 40 ms 384 KB Output is correct
7 Correct 47 ms 512 KB Output is correct
8 Correct 41 ms 384 KB Output is correct
9 Correct 48 ms 384 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 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 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 392 KB Output is correct

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Incorrect 43 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 Correct 40 ms 384 KB Output is correct
4 Correct 40 ms 384 KB Output is correct
5 Correct 40 ms 384 KB Output is correct
6 Correct 40 ms 384 KB Output is correct
7 Correct 47 ms 512 KB Output is correct
8 Correct 41 ms 384 KB Output is correct
9 Correct 48 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 392 KB Output is correct
28 Correct 1 ms 416 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Incorrect 43 ms 384 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -