oj.uz

Submission #606274

# Submission time Handle Problem Language Result Execution time Memory
606274 2022-07-26T05:55:08 Z Jarif_Rahman ICC (CEOI16_icc) C++17
100 / 100
 124 ms 616 KB 
#include "icc.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

bool Query(vector<int> _A, vector<int> _B){
    int a = _A.size(), b = _B.size();
    int A[a], B[b];
    for(int i = 0; i < a; i++) A[i] = _A[i]+1;
    for(int i = 0; i < b; i++) B[i] = _B[i]+1;
    return query(a, b, A, B);
}

void SetRoad(int a, int b){
    setRoad(a+1, b+1);
}

void run(int n){
    vector<vector<int>> comps(n);

    for(int i = 0; i < n; i++) comps[i].pb(i);

    for(int I = 0; I < n-1; I++){
        int c = comps.size();
        int k = 1, xr = 0;

        while(k <= c-1){
            vector<int> s0, s1;
            for(int i = 0; i < c; i++){
                if(i&k) for(int x: comps[i]) s1.pb(x);
                else for(int x: comps[i]) s0.pb(x);
            }

            if(Query(s0, s1)) xr+=k;
            k*=2;
        }

        vector<int> s;
        for(int i = 0; i < c; i++){
            if((i^xr) < i || (i^xr) >= c) continue;
            s.pb(i);
        }

        int a = 0, b = int(s.size())-1;
        while(a < b){
            int md = (a+b)/2;
            vector<int> s1, s2;
            for(int i = 0; i <= md; i++){
                for(int x: comps[s[i]]) s1.pb(x);
                for(int x: comps[s[i]^xr]) s2.pb(x);
            }

            if(Query(s1, s2)) b = md;
            else a = md+1;
        }

        int A = s[a], B = s[a]^xr;

        a = 0, b = int(comps[B].size())-1;
        while(a < b){
            int md = (a+b)/2;
            vector<int> ss(comps[B].begin(), comps[B].begin()+md+1);
            if(Query(comps[A], ss)) b = md;
            else a = md+1;
        }
        int node_b = comps[B][a];

        a = 0, b = int(comps[A].size())-1;
        while(a < b){
            int md = (a+b)/2;
            vector<int> ss(comps[A].begin(), comps[A].begin()+md+1);
            if(Query(ss, {node_b})) b = md;
            else a = md+1;
        }
        int node_a = comps[A][a];

        SetRoad(node_a, node_b);

        if(comps[A].size() < comps[B].size()) swap(comps[A], comps[B]);
        while(!comps[B].empty()){
            comps[A].pb(comps[B].back());
            comps[B].pop_back();
        }

        comps.erase(comps.begin()+B);
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 109 queries used.
2 Correct 5 ms 468 KB Ok! 107 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 380 KB Ok! 616 queries used.
2 Correct 26 ms 496 KB Ok! 459 queries used.
3 Correct 25 ms 496 KB Ok! 518 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 488 KB Ok! 1538 queries used.
2 Correct 93 ms 504 KB Ok! 1077 queries used.
3 Correct 124 ms 468 KB Ok! 1524 queries used.
4 Correct 106 ms 468 KB Ok! 1514 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 504 KB Ok! 1454 queries used.
2 Correct 109 ms 500 KB Ok! 1473 queries used.
3 Correct 107 ms 488 KB Ok! 1481 queries used.
4 Correct 104 ms 488 KB Ok! 1530 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 484 KB Ok! 1483 queries used.
2 Correct 93 ms 488 KB Ok! 1450 queries used.
3 Correct 94 ms 508 KB Ok! 1343 queries used.
4 Correct 104 ms 468 KB Ok! 1492 queries used.
5 Correct 101 ms 616 KB Ok! 1519 queries used.
6 Correct 99 ms 492 KB Ok! 1528 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 588 KB Ok! 1444 queries used.
2 Correct 92 ms 488 KB Ok! 1259 queries used.