oj.uz

Submission #230983

# Submission time Handle Problem Language Result Execution time Memory
230983 2020-05-12T09:06:18 Z PeppaPig Chameleon's Love (JOI20_chameleon) C++14
40 / 100
 45 ms 768 KB 
#include "chameleon.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 505;

int same[N], nex[N], pre[N];
vector<int> g[N];

bool find_edge(vector<int> v, int x) {
    v.emplace_back(x);
    return Query(v) < v.size();
}

void Solve(int n) {
    n *= 2;
    for(int i = 1; i <= n; i++) {
        vector<int> col(n + 1), vec[3];
        function<void(int, int)> dfs = [&](int u, int c) {
            col[u] = c;
            for(int v : g[u]) if(!col[v]) dfs(v, c ^ 3);
        };
        for(int j = 1; j < i; j++) {
            if(!col[j]) dfs(j, 1);
            vec[col[j]].emplace_back(j);
        }
        for(int j = 1; j <= 2; j++) {
            vector<int> now = vec[j];
            while(find_edge(now, i)) {
                int l = 0, r = now.size() - 1;
                while(l < r) {
                    int mid = (l + r) >> 1;
                    vector<int> v(now.begin(), now.begin() + mid + 1);
                    if(find_edge(v, i)) r = mid;
                    else l = mid + 1;
                }
                g[now[r]].emplace_back(i), g[i].emplace_back(now[r]);
                now = vector<int>(now.begin() + r + 1, now.end());
            }
        }
    }

    for(int i = 1; i <= n; i++) {
        if(g[i].size() == 1) same[i] = g[i][0];
        else {
            do if(Query({i, g[i][0], g[i][1]}) == 1) {
                nex[i] = g[i][2], pre[g[i][2]] = i;
                break;
            } while(next_permutation(g[i].begin(), g[i].end()));
        }
    }
    for(int i = 1; i <= n; i++) {
        if(!same[i]) same[i] = g[i][0] + g[i][1] + g[i][2] - nex[i] - pre[i];
        if(i < same[i]) Answer(i, same[i]);
    }
}

Compilation message

chameleon.cpp: In function 'bool find_edge(std::vector<int>, int)':
chameleon.cpp:13:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return Query(v) < v.size();
            ~~~~~~~~~^~~~~~~~~~

Subtask #1
0 / 4.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 Runtime error 33 ms 568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 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 4 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 4 ms 384 KB Output is correct
2 Correct 4 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 4 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 5 ms 384 KB Output is correct
11 Correct 6 ms 384 KB Output is correct
12 Correct 6 ms 384 KB Output is correct
13 Correct 5 ms 384 KB Output is correct
14 Correct 6 ms 336 KB Output is correct
15 Correct 5 ms 384 KB Output is correct
16 Correct 5 ms 384 KB Output is correct
17 Correct 6 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 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Runtime error 45 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
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 384 KB Output is correct
3 Runtime error 33 ms 568 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -