oj.uz

Submission #604342

# Submission time Handle Problem Language Result Execution time Memory
604342 2022-07-25T04:21:02 Z tranxuanbach ICC (CEOI16_icc) C++17
100 / 100
 124 ms 596 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 468 KB Ok! 98 queries used.
2 Correct 5 ms 468 KB Ok! 103 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 588 KB Ok! 533 queries used.
2 Correct 30 ms 468 KB Ok! 627 queries used.
3 Correct 36 ms 484 KB Ok! 639 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 508 KB Ok! 1460 queries used.
2 Correct 111 ms 492 KB Ok! 1539 queries used.
3 Correct 107 ms 500 KB Ok! 1556 queries used.
4 Correct 115 ms 496 KB Ok! 1525 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 504 KB Ok! 1551 queries used.
2 Correct 108 ms 504 KB Ok! 1528 queries used.
3 Correct 104 ms 596 KB Ok! 1561 queries used.
4 Correct 105 ms 496 KB Ok! 1516 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 118 ms 504 KB Ok! 1555 queries used.
2 Correct 110 ms 492 KB Ok! 1557 queries used.
3 Correct 110 ms 468 KB Ok! 1567 queries used.
4 Correct 106 ms 504 KB Ok! 1572 queries used.
5 Correct 99 ms 492 KB Ok! 1522 queries used.
6 Correct 118 ms 504 KB Ok! 1558 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 500 KB Ok! 1572 queries used.
2 Correct 106 ms 496 KB Ok! 1559 queries used.