Submission #605675

#	Time	Username	Problem	Language	Result	Execution time	Memory
605675		2fat2code	ICC (CEOI16_icc)	C++17	100 / 100	132 ms	500 KiB

icc

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