oj.uz

Submission #895368

# Submission time Handle Problem Language Result Execution time Memory
895368 2023-12-29T19:42:56 Z box Chameleon's Love (JOI20_chameleon) C++17
60 / 100
 23 ms 600 KB 
#include <bits/stdc++.h>
#include "chameleon.h"
using namespace std;

#define ar array
#define sz(v) int(std::size(v))
using i64 = long long;
using vi = vector<int>;

const int MAXN = 505 * 2;

vi adj[MAXN];
int who[MAXN], nex[MAXN], pre[MAXN];

vi operator+(vi one, const vi two) {
    one.insert(end(one), begin(two), end(two));
    return one;
}
bool interesting(vi one) {
    return Query(one) != sz(one);
}

void Solve(int N) {
    if (N <= 50) {
        for (int i = 1; i <= N * 2; i++)
            for (int j = i + 1; j <= N * 2; j++)
                if (Query({i, j}) == 1) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
    } else {
        vi base(N);
        iota(begin(base), end(base), 1);
        for (int i = N + 1; i <= N * 2; i++) {
            vi v = base;
            while (interesting(v + vi{{i}})) {
                int low = 0, hi = sz(v) - 1;
                while (low < hi) {
                    int m = (low + hi) / 2;
                    interesting(vi(begin(v), begin(v) + m + 1) + vi{{i}}) ? hi = m : low = m + 1;
                }
                adj[v[low]].push_back(i);
                adj[i].push_back(v[low]);
                v = vi(begin(v) + low + 1, end(v));
            }
        }
    }
    for (int i = 1; i <= N * 2; i++) {
        assert(sz(adj[i]) == 1 || sz(adj[i]) == 3);
        if (sz(adj[i]) == 1) {
            who[i] = adj[i][0];
        } else {
            nex[i] = [&]() {
                if (Query({i, adj[i][0], adj[i][1]}) == 1) return adj[i][2];
                if (Query({i, adj[i][0], adj[i][2]}) == 1) return adj[i][1];
                return adj[i][0];
            }();
            pre[nex[i]] = i;
        }
    }
    for (int i = 1; i <= N * 2; i++) {
        if (!who[i]) {
            assert(sz(adj[i]) == 3);
            assert(pre[i] && nex[i]);
            who[i] = adj[i][0] ^ adj[i][1] ^ adj[i][2] ^ pre[i] ^ nex[i];
        }
        if (who[i] < i) Answer(who[i], i);
    }
}

Subtask #1
0 / 4.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
20.0 / 20.0

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

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 23 ms 564 KB Output is correct
4 Correct 22 ms 600 KB Output is correct
5 Correct 22 ms 344 KB Output is correct
6 Correct 23 ms 344 KB Output is correct
7 Correct 22 ms 572 KB Output is correct
8 Correct 23 ms 344 KB Output is correct
9 Correct 22 ms 344 KB Output is correct

Subtask #5
0 / 36.0

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