Submission #105413

#	Time	Username	Problem	Language	Result	Execution time	Memory
105413		alexpetrescu	ICC (CEOI16_icc)	C++14	100 / 100	157 ms	632 KiB

icc

#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 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10