oj.uz

답안 #706878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
706878 2023-03-08T02:39:35 Z vjudge1 CEOI16_icc (CEOI16_icc) C++17
100 / 100
 119 ms 620 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

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 468 KB Ok! 96 queries used.
2 Correct 5 ms 468 KB Ok! 95 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 26 ms 468 KB Ok! 529 queries used.
2 Correct 31 ms 484 KB Ok! 627 queries used.
3 Correct 32 ms 468 KB Ok! 636 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 102 ms 492 KB Ok! 1464 queries used.
2 Correct 106 ms 512 KB Ok! 1551 queries used.
3 Correct 103 ms 500 KB Ok! 1579 queries used.
4 Correct 119 ms 512 KB Ok! 1534 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 107 ms 620 KB Ok! 1548 queries used.
2 Correct 113 ms 620 KB Ok! 1556 queries used.
3 Correct 106 ms 500 KB Ok! 1575 queries used.
4 Correct 103 ms 508 KB Ok! 1529 queries used.

Subtask #5
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 104 ms 500 KB Ok! 1569 queries used.
2 Correct 105 ms 504 KB Ok! 1574 queries used.
3 Correct 119 ms 508 KB Ok! 1565 queries used.
4 Correct 105 ms 508 KB Ok! 1583 queries used.
5 Correct 100 ms 468 KB Ok! 1523 queries used.
6 Correct 105 ms 496 KB Ok! 1560 queries used.

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 114 ms 508 KB Ok! 1579 queries used.
2 Correct 108 ms 512 KB Ok! 1564 queries used.