Submission #604342

#	Time	Username	Problem	Language	Result	Execution time	Memory
604342		tranxuanbach	ICC (CEOI16_icc)	C++17	100 / 100	124 ms	596 KiB

icc

#ifndef FEXT

#include "icc.h"

#endif

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

// #define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())

using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;

mt19937 rando(chrono::steady_clock::now().time_since_epoch().count());
int randt(int l, int r){
    return rando() % (r - l + 1) + l;
}

#ifdef FEXT

int query(int sza, int szb, int a[], int b[]){
    cout << "query " << sza << ' ' << szb << endl;
    For(i, 0, sza){
        cout << a[i] << ' ';
    } cout << endl;
    For(i, 0, szb){
        cout << b[i] << ' ';
    } cout << endl;
    int ans; cin >> ans; return ans;
}

void setRoad(int u, int v){
    cout << "setRoad " << u << ' ' << v << endl;
}

#endif

const int N = 1e2 + 5;

int querya[N], queryb[N];

int realquery(vi a, vi b){
    int idxa = 0, idxb = 0;
    Fora(i, a){
        querya[idxa++] = i + 1;
    }
    Fora(i, b){
        queryb[idxb++] = i + 1;
    }
    return query(idxa, idxb, querya, queryb);
}

void realsetRoad(int u, int v){
    u++; v++;
    setRoad(u, v);
}

int n, m;
int idxgroup[N];

void shuffle_group(){
    vi group(idxgroup, idxgroup + n);
    sort(bend(group)); group.erase(unique(bend(group)), group.end());
    vi permgroup(m);
    iota(bend(permgroup), 0);
    shuffle(bend(permgroup), rando);
    For(u, 0, n){
        idxgroup[u] = permgroup[lower_bound(bend(group), idxgroup[u]) - group.begin()];
    }
}

void run(int _n){
n = _n;
m = n;
For(u, 0, n){
    idxgroup[u] = u;
}
ForE(turn, 1, n - 1){
    shuffle_group();

    // cout << "group" << endl;
    // For(u, 0, n){
    //     cout << idxgroup[u] << ' ';
    // } cout << endl;

    vi a, b;
    int bit = 0;
    while (1){
        vi c, d;
        For(u, 0, n){
            if (idxgroup[u] >> bit & 1){
                d.emplace_back(u);
            }
            else{
                c.emplace_back(u);
            }
        }
        if (__lg(m) == bit or realquery(c, d)){
            a = c; b = d;
            break;
        }
        bit++;
    }
    while (isz(a) != 1){
        vi al(a.begin(), a.begin() + isz(a) / 2), ar(a.begin() + isz(a) / 2, a.end());
        if (realquery(al, b)){
            a = al;
        }
        else{
            a = ar;
        }
    }
    while (isz(b) != 1){
        vi bl(b.begin(), b.begin() + isz(b) / 2), br(b.begin() + isz(b) / 2, b.end());
        if (realquery(a, bl)){
            b = bl;
        }
        else{
            b = br;
        }
    }
    realsetRoad(a[0], b[0]);
    int g = idxgroup[b[0]];
    For(u, 0, n){
        if (idxgroup[u] == g){
            idxgroup[u] = idxgroup[a[0]];
        }
    }

    m--;
}
}

#ifdef FEXT

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("KEK.inp", "r", stdin);
    // freopen("KEK.out", "w", stdout);
    int n; cin >> n;
    run(n);
}

#endif

/*
==================================================+
INPUT:                                            |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
OUTPUT:                                           |
--------------------------------------------------|

--------------------------------------------------|
==================================================+
*/

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