oj.uz

Submission #96867

# Submission time Handle Problem Language Result Execution time Memory
96867 2019-02-12T14:18:22 Z Kastanda ICC (CEOI16_icc) C++11
100 / 100
 159 ms 636 KB 
// I do it for the glory
#include<bits/stdc++.h>
#include "icc.h"
#define pb push_back
using namespace std;
//mt19937 Rnd(chrono::steady_clock::now().time_since_epoch().count());
int fe, se;
void GoForIt(vector < int > L, vector < int > R)
{
    int cnt = 0;
    while (L.size() > 1)
    {
        vector < int > L1, L2;
        for (int i = 0; i < (int)L.size(); i++)
        {
            if (i < (((int)L.size() + 1) >> 1))
                L1.pb(L[i]);
            else
                L2.pb(L[i]);
        }
        cnt ++;
        bool w = query(L1.size(), R.size(), L1.data(), R.data());
        if (w) L = L1;
        else L = L2;
    }
    while (R.size() > 1)
    {
        vector < int > R1, R2;
        for (int i = 0; i < (int)R.size(); i++)
        {
            if (i < (((int)R.size() + 1) >> 1))
                R1.pb(R[i]);
            else
                R2.pb(R[i]);
        }
        cnt ++;
        bool w = query(L.size(), R1.size(), L.data(), R1.data());
        if (w) R = R1;
        else R = R2;
    }
    assert(cnt <= 13);
    fe = L[0];
    se = R[0];
    return ;
}
void run(int N)
{
    int P[N + 1];
    set < int > S;
    vector < int > A[N + 1];
    for (int i = 1; i <= N; i++)
        A[i].pb(i), P[i] = i, S.insert(i);
    for (int q = 1; q <= N - 1; q ++)
    {
        vector < int > L, R, perm(7, 0);
        //iota(perm.begin(), perm.end(), 0);
        //auto it = perm.begin(); it ++;
        //shuffle(it, perm.end(), Rnd);
        for (int bit = 0; bit <= 7; bit ++)
        {
            L.clear(); R.clear();
            int id = 0;
            for (int i : S)
            {
                id ++;
                bool w = (id & (1 << bit)) ? (1) : (0);
                for (int v : A[i])
                {
                    if (w) L.pb(v);
                    else R.pb(v);
                }
            }
            if (!L.size() || !R.size())
                continue; // What are the odds of that ?
            if (query(L.size(), R.size(), L.data(), R.data()))
                break;
        }
        GoForIt(L, R);
        setRoad(fe, se);
        int v = se, u = fe;
        int pu = P[u];
        for (int w : A[pu])
            P[w] = P[v], A[P[v]].pb(w);
        A[pu].clear(); S.erase(pu);
    }
    return ;
}
// Oh com on b*tch

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 512 KB Ok! 99 queries used.
2 Correct 9 ms 512 KB Ok! 92 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 512 KB Ok! 526 queries used.
2 Correct 44 ms 636 KB Ok! 657 queries used.
3 Correct 50 ms 512 KB Ok! 647 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 576 KB Ok! 1426 queries used.
2 Correct 151 ms 568 KB Ok! 1596 queries used.
3 Correct 143 ms 564 KB Ok! 1582 queries used.
4 Correct 135 ms 512 KB Ok! 1463 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 512 KB Ok! 1526 queries used.
2 Correct 137 ms 512 KB Ok! 1461 queries used.
3 Correct 145 ms 512 KB Ok! 1561 queries used.
4 Correct 135 ms 616 KB Ok! 1483 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 632 KB Ok! 1571 queries used.
2 Correct 149 ms 568 KB Ok! 1538 queries used.
3 Correct 159 ms 572 KB Ok! 1610 queries used.
4 Correct 142 ms 512 KB Ok! 1557 queries used.
5 Correct 141 ms 484 KB Ok! 1455 queries used.
6 Correct 145 ms 512 KB Ok! 1528 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 572 KB Ok! 1569 queries used.
2 Correct 144 ms 512 KB Ok! 1599 queries used.