oj.uz

Submission #96834

# Submission time Handle Problem Language Result Execution time Memory
96834 2019-02-12T12:58:31 Z Kastanda ICC (CEOI16_icc) C++11
61 / 100
 212 ms 760 KB 
// I do it for the glory
#include<bits/stdc++.h>
#include "icc.h"
#define pb push_back
using namespace std;
mt19937 Rnd(time(0));
int fe, se;
bool Rand()
{
    return (Rnd() & 1);
}
void GoForIt(vector < int > L, vector < int > R)
{
    if (L.size() > R.size())
        L.swap(R);
    if (R.size() == 1)
    {
        fe = L[0];
        se = R[0];
        return ;
    }
    vector < int > R1, R2;
    for (int i = 0; i < (int)R.size(); i++)
    {
        if (i < (R.size() >> 1))
            R1.pb(R[i]);
        else
            R2.pb(R[i]);
    }
    R.clear();
    bool w = query(L.size(), R1.size(), L.data(), R1.data());
    if (w) GoForIt(L, R1);
    else GoForIt(L, R2);
}
void run(int N)
{
    int P[N + 1];
    vector < int > A[N + 1];
    for (int i = 1; i <= N; i++)
        A[i].pb(i), P[i] = i;
    for (int q = 1; q <= N - 1; q ++)
    {
        bool done = 0;
        vector < int > L, R;
        while (!done)
        {
            L.clear(); R.clear();
            for (int i = 1; i <= N; i++)
            {
                bool w = Rand();
                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 ?
            done = query(L.size(), R.size(), L.data(), R.data());
        }
        GoForIt(L, R);
        setRoad(fe, se);
        int v = fe, u = se, pu = P[u];
        for (int w : A[pu])
            P[w] = P[v], A[P[v]].pb(w);
        A[pu].clear();
    }
    return ;
}

Compilation message

icc.cpp: In function 'void GoForIt(std::vector<int>, std::vector<int>)':
icc.cpp:25:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (i < (R.size() >> 1))
             ~~^~~~~~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 512 KB Ok! 552 queries used.
2 Correct 66 ms 640 KB Ok! 841 queries used.
3 Correct 63 ms 512 KB Ok! 811 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 640 KB Ok! 1532 queries used.
2 Correct 212 ms 576 KB Ok! 2154 queries used.
3 Correct 177 ms 632 KB Ok! 1731 queries used.
4 Correct 173 ms 632 KB Ok! 1788 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 171 ms 512 KB Ok! 1658 queries used.
2 Correct 165 ms 632 KB Ok! 1686 queries used.
3 Correct 154 ms 512 KB Ok! 1825 queries used.
4 Correct 161 ms 584 KB Ok! 1632 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 760 KB Too many queries! 1938 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 168 ms 512 KB Too many queries! 1919 out of 1625
2 Halted 0 ms 0 KB -