oj.uz

Submission #105413

# Submission time Handle Problem Language Result Execution time Memory
105413 2019-04-12T04:29:38 Z alexpetrescu ICC (CEOI16_icc) C++14
100 / 100
 157 ms 632 KB 
#include <cstdio>
#include "icc.h"
#include <vector>

#define vec std::vector

#define MAXN 100

int queryA[MAXN], queryB[MAXN], a[MAXN], b[MAXN];
std::vector < int > arb[MAXN];

inline int myQuery(vec < int > A, vec < int > B) {
    int size_a = 0, size_b = 0;
    for (auto &x : A)
        for (auto &y : arb[x])
            queryA[size_a++] = y;
    for (auto &x : B)
        for (auto &y : arb[x])
            queryB[size_b++] = y;
    return query(size_a, size_b, queryA, queryB);
}

inline void solve(int sizeA, int sizeB, int a[], int b[]) {
    while (sizeA > 1) {
        int mySize = 0;
        for (int i = 0; i < sizeA / 2; i++)
            queryA[mySize++] = a[i];
        if (query(mySize, sizeB, queryA, b))
            sizeA = mySize;
        else {
            sizeA -= mySize;
            for (int i = 0; i < sizeA; i++)
                a[i] = a[i + mySize];
        }
    }
}

inline void scoate(int &N, int x) {
    std::swap(arb[x], arb[N - 1]);
    N--;
}

inline void un_pas(int &N) {
    int myXor = 0;
    for (int i = 0; (1 << i) <= N - 1; i++) {
        vec < int > a[2];
        for (int j = 0; j < N; j++)
            a[bool(j & (1 << i))].push_back(j);
        myXor ^= myQuery(a[0], a[1]) << i;
    }

    vec < int > viz(N, 0), val;
    for (int i = 0; i < N; i++) {
        if (viz[i] == 0 && (i ^ myXor) < N) {
            viz[i] = viz[i ^ myXor] = 1;
            val.push_back(i);
        }
    }

    while ((int)val.size() > 1) {
        vec < int > mult, other;
        for (int i = 0; i < (int)val.size() / 2; i++)
            mult.push_back(val[i]);
        for (auto &x : mult)
            other.push_back(x ^ myXor);
        if (!myQuery(mult, other)) {
            mult.clear();
            for (int i = val.size() / 2; i < (int)val.size(); i++)
                mult.push_back(val[i]);
        }
        val = mult;
    }

    int sizeA = 0, sizeB = 0;
    for (auto &x : arb[val[0]])
        a[sizeA++] = x;
    for (auto &x : arb[val[0] ^ myXor])
        b[sizeB++] = x;
    solve(sizeA, sizeB, a, b);
    solve(sizeB, sizeA, b, a);

    setRoad(a[0], b[0]);

    vec < int > last = arb[val[0]];
    for (auto &x : arb[val[0] ^ myXor])
        last.push_back(x);
    std::swap(arb[val[0]], arb[N - 1]);
    if ((val[0] ^ myXor) != N - 1)
        std::swap(arb[val[0] ^ myXor], arb[N - 2]);
    else
        std::swap(arb[val[0]], arb[N - 2]);
    N--;
    arb[N - 1] = last;
}

void run(int N) {
    for (int i = 0; i < N; i++)
        arb[i].push_back(i + 1);
    while (N > 1)
        un_pas(N);
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Ok! 110 queries used.
2 Correct 11 ms 512 KB Ok! 105 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 512 KB Ok! 595 queries used.
2 Correct 51 ms 632 KB Ok! 592 queries used.
3 Correct 43 ms 512 KB Ok! 599 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 151 ms 512 KB Ok! 1539 queries used.
2 Correct 129 ms 604 KB Ok! 1493 queries used.
3 Correct 118 ms 568 KB Ok! 1493 queries used.
4 Correct 150 ms 600 KB Ok! 1483 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 122 ms 576 KB Ok! 1488 queries used.
2 Correct 140 ms 584 KB Ok! 1461 queries used.
3 Correct 119 ms 576 KB Ok! 1493 queries used.
4 Correct 131 ms 604 KB Ok! 1507 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 131 ms 608 KB Ok! 1493 queries used.
2 Correct 131 ms 604 KB Ok! 1493 queries used.
3 Correct 113 ms 564 KB Ok! 1495 queries used.
4 Correct 157 ms 604 KB Ok! 1498 queries used.
5 Correct 129 ms 616 KB Ok! 1518 queries used.
6 Correct 136 ms 512 KB Ok! 1487 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 132 ms 604 KB Ok! 1493 queries used.
2 Correct 125 ms 568 KB Ok! 1493 queries used.