oj.uz

Submission #605675

# Submission time Handle Problem Language Result Execution time Memory
605675 2022-07-25T21:54:50 Z 2fat2code ICC (CEOI16_icc) C++17
100 / 100
 132 ms 500 KB 
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

const int nmax = 105;

int par[nmax];
vector<int>componente[nmax];

void run(int n){
    for(int i=1;i<=n;i++){
        componente[i].push_back(i);
        par[i] = i;
    }
    int nrcomponente = n;
    vector<int>cautambinar_A, cautambinar_B;
    for(int i=1;i<n;i++){
        int bit = 0, xr = 0;
        while((1<<bit) <= nrcomponente){
            int a_sz = 0; vector<int>a;
            int b_sz = 0; vector<int>b;
            for(int j=1;j<=nrcomponente;j++){
                if(j & (1 << bit)){
                    a_sz += componente[j].size();
                    for(auto it : componente[j]) a.push_back(it);
                }
                else{
                    b_sz += componente[j].size();
                    for(auto it : componente[j]) b.push_back(it);
                }
            }
            if(query(a_sz, b_sz, a.data(), b.data()) == 1){
                xr += (1 << bit);
                cautambinar_A = a;
                cautambinar_B = b;
            }
            ++bit;
        }
        int l = 0, r = cautambinar_A.size() - 1, ok = 0;
        vector<int>tz;
        while(l <= r){
            int mid = l + (r - l) / 2;
            tz.clear();
            for(int j=0;j<=mid;j++) tz.push_back(cautambinar_A[j]);
            if(query(tz.size(), cautambinar_B.size(), tz.data(), cautambinar_B.data())){
                ok = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
        }
        ok = cautambinar_A[ok];
        xr ^= par[ok];
        int ok2 = 0;
        l = 0, r = componente[xr].size() - 1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            tz.clear();
            for(int j=0;j<=mid;j++){
                tz.push_back(componente[xr][j]);
            }
            if(!query(1, tz.size(), &ok, tz.data())){
                l = mid + 1;
            }
            else{
                ok2 = mid;
                r = mid - 1;
            }
        }
        ok2 = componente[xr][ok2];
        int lmao = max(par[ok], par[ok2]);
        int slavic = min(par[ok], par[ok2]);
        for(int j=1;j<=n;j++){
            if(par[j] == lmao) par[j] = slavic;
            else if(par[j] > lmao){
                par[j]--;
            }
        }
        for(int j=1;j<=nrcomponente;j++) componente[j].clear();
        for(int j=1;j<=n;j++) componente[par[j]].push_back(j);
        setRoad(ok, ok2);
        nrcomponente--;
    }
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 468 KB Ok! 120 queries used.
2 Correct 8 ms 468 KB Ok! 120 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 500 KB Ok! 616 queries used.
2 Correct 33 ms 468 KB Ok! 567 queries used.
3 Correct 37 ms 480 KB Ok! 597 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 488 KB Ok! 1444 queries used.
2 Correct 104 ms 500 KB Ok! 1286 queries used.
3 Correct 132 ms 484 KB Ok! 1558 queries used.
4 Correct 112 ms 496 KB Ok! 1518 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 500 KB Ok! 1508 queries used.
2 Correct 116 ms 496 KB Ok! 1536 queries used.
3 Correct 118 ms 488 KB Ok! 1544 queries used.
4 Correct 115 ms 496 KB Ok! 1541 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 496 KB Ok! 1547 queries used.
2 Correct 116 ms 480 KB Ok! 1510 queries used.
3 Correct 114 ms 484 KB Ok! 1487 queries used.
4 Correct 117 ms 484 KB Ok! 1537 queries used.
5 Correct 110 ms 480 KB Ok! 1441 queries used.
6 Correct 121 ms 488 KB Ok! 1498 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 484 KB Ok! 1484 queries used.
2 Correct 112 ms 496 KB Ok! 1445 queries used.