oj.uz

Submission #213315

# Submission time Handle Problem Language Result Execution time Memory
213315 2020-03-25T13:54:35 Z popovicirobert Chameleon's Love (JOI20_chameleon) C++14
44 / 100
 93 ms 636 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1000;

static vector<int> g[MAXN + 1];
static vector<int> side[2];
static bool vis[MAXN + 1];

void dfs(int nod, int col) {
    if(vis[nod]) return ;
    vis[nod] = 1;
    side[col].push_back(nod);
    for(auto it : g[nod]) {
        dfs(it, col ^ 1);
    }
}

void Solve(int n) {
    vector<set<int>> all(2 * n + 1);
    for(int i = 1; i <= 2 * n; i++) {
        for(int t = 0; t < 2; t++) {
            int x = -1, sz = side[t].size();
            while(x < sz) {
                int y = x;
                for(int step = 1 << 9; step; step >>= 1) {
                    if(y + step < sz) {
                        vector<int> cur;
                        cur.push_back(i);
                        for(int j = x + 1; j <= y + step; j++) {
                            cur.push_back(side[t][j]);
                        }
                        if(Query(cur) == cur.size()) {
                            y += step;
                        }
                    }
                }
                y++;
                if(y < sz) {
                    all[i].insert(side[t][y]);
                    all[side[t][y]].insert(i);
                    g[i].push_back(side[t][y]);
                    g[side[t][y]].push_back(i);
                }
                x = y;
            }
            side[t].clear();
        }
        fill(vis, vis + i + 1, 0);
        for(int j = 1; j <= i; j++) {
            dfs(j, 0);
        }
    }
    for(int i = 1; i <= 2 * n; i++) {
        g[i].clear();
    }
    for(int i = 1; i <= 2 * n; i++) {
        vector<int> cur;
        for(auto it : all[i]) {
            cur.push_back(it);
        }
        int j;
        if(cur.size() == 3) {
            if(Query({i, cur[0], cur[1]}) == 1) {
                j = cur[2];
            }
            else if(Query({i, cur[1], cur[2]}) == 1) {
                j = cur[0];
            }
            else {
                j = cur[1];
            }
            g[i].push_back(j);
            g[j].push_back(i);
        }
    }
    for(int i = 1; i <= 2 * n; i++) {
        for(auto it : g[i]) {
            if(all[i].count(it)) {
                all[i].erase(it);
            }
        }
        assert(all[i].size() == 1);
        if(*all[i].begin() > i) {
            Answer(i, *all[i].begin());
        }
    }
}

Compilation message

chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:35:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(Query(cur) == cur.size()) {
                            ~~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 67 ms 512 KB Output is correct
4 Correct 67 ms 512 KB Output is correct
5 Correct 67 ms 512 KB Output is correct
6 Correct 67 ms 512 KB Output is correct
7 Correct 67 ms 512 KB Output is correct
8 Correct 68 ms 512 KB Output is correct
9 Correct 68 ms 512 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
0 / 20.0

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

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 67 ms 512 KB Output is correct
4 Correct 67 ms 512 KB Output is correct
5 Correct 67 ms 512 KB Output is correct
6 Correct 67 ms 512 KB Output is correct
7 Correct 67 ms 512 KB Output is correct
8 Correct 68 ms 512 KB Output is correct
9 Correct 68 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 5 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
19 Correct 6 ms 384 KB Output is correct
20 Correct 5 ms 384 KB Output is correct
21 Correct 6 ms 384 KB Output is correct
22 Correct 6 ms 384 KB Output is correct
23 Correct 6 ms 384 KB Output is correct
24 Correct 5 ms 384 KB Output is correct
25 Correct 6 ms 384 KB Output is correct
26 Correct 6 ms 384 KB Output is correct
27 Correct 6 ms 384 KB Output is correct
28 Correct 5 ms 384 KB Output is correct
29 Correct 5 ms 384 KB Output is correct
30 Incorrect 93 ms 636 KB Wrong Answer [3]
31 Halted 0 ms 0 KB -