Submission #706950

#	Time	Username	Problem	Language	Result	Execution time	Memory
706950		baokhue232005	ICC (CEOI16_icc)	C++14	100 / 100	127 ms	7684 KiB

icc

/*
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
*/
// lethal option

#include "icc.h"
#include<bits/stdc++.h>
using namespace std;

#define all(flg) flg.begin(), flg.end()
#define pb push_back
#define fi first
#define se second
#define endl "\n"
#define eb emplace_back
#define ii pair<int, int>
#define vi vector<int>
#define PI 3.141592653589793238462643383279502884
#define ll long long
#define ld long double
#define for1(i, ff, gg) for(int i = ff; i <= gg; ++i)
#define for2(i, ff, gg) for(int i = ff; i >= gg; --i)
const ll mod = 1e9 + 7;
const int maxN = 300005;
const ll oo = 1e18 + 7;
int n, a[maxN];
int x, y, z, k;

vi bag[maxN];
int cnt = 0;
int par[maxN];

int find(int i){
    if(i == par[i]) return i;
    return par[i] = find(par[i]);
}
/*
void setRoad(int n1, int n2){

}

int query(int n1, int n2, vi f1, vi f2){
    return 1;
}
*/
int spec_qry(vi f1, vi f2){
    return query(f1.size(), f2.size(), &f1[0], &f2[0]);
}

int qry(vi f1, vi f2){
    vi co1, co2;
    for(int id : f1) for(int cc : bag[id]) co1.pb(cc);
    for(int id : f2) for(int cc : bag[id]) co2.pb(cc);
    return spec_qry(co1, co2);
}

void run(int N){
    n = N;
    for1(i, 1, n) par[i] = i;
    for1(whattheactual, 2, n){
        for1(i, 1, n) bag[i].clear();
        for1(i, 1, n) bag[find(i)].pb(i);
        cnt = 0;
        for1(i, 1, n) if(bag[i].size()) swap(bag[cnt++], bag[i]);
        vi c1, c2;
        for1(bt, 0, mod){
            c1.clear();
            c2.clear();
            for1(i, 0, cnt - 1){
                if(i & (1 << bt)) c1.pb(i);
                else c2.pb(i);
            }
            if(qry(c1, c2)) break;
        }
        vi co1, co2;
        for(int id : c1) for(int cc : bag[id]) co1.pb(cc);
        for(int id : c2) for(int cc : bag[id]) co2.pb(cc);
        for1(dumb, 0, 1){
            swap(co1, co2);
            while(co1.size() > 1){
                vi f1, f2;
                x = 0;
                for(int cc : co1){
                    if(x) f1.pb(cc);
                    else f2.pb(cc);
                    x = !x;
                }
                if(spec_qry(f1, co2)) co1 = f1;
                else co1 = f2;
            }
        }
        int n1 = co1[0]; int n2 = co2[0];
        setRoad(n1, n2);
        par[find(n1)] = find(n2);
    }
}
/*
signed main(){
    // freopen(".inp", "r", stdin);
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

}
*/

• Subtask 1: 7 / 7
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 21 / 21
• Subtask 5: 29 / 29
• Subtask 6: 10 / 10