oj.uz

Submission #706949

# Submission time Handle Problem Language Result Execution time Memory
706949 2023-03-08T07:10:12 Z vjudge1 ICC (CEOI16_icc) C++17
100 / 100
 106 ms 7676 KB 
/*
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7508 KB Ok! 96 queries used.
2 Correct 8 ms 7556 KB Ok! 97 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 7560 KB Ok! 545 queries used.
2 Correct 36 ms 7544 KB Ok! 660 queries used.
3 Correct 36 ms 7540 KB Ok! 667 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 7508 KB Ok! 1504 queries used.
2 Correct 106 ms 7560 KB Ok! 1619 queries used.
3 Correct 102 ms 7576 KB Ok! 1624 queries used.
4 Correct 102 ms 7508 KB Ok! 1548 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 7556 KB Ok! 1553 queries used.
2 Correct 101 ms 7628 KB Ok! 1535 queries used.
3 Correct 99 ms 7628 KB Ok! 1619 queries used.
4 Correct 96 ms 7568 KB Ok! 1485 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 7552 KB Ok! 1615 queries used.
2 Correct 100 ms 7560 KB Ok! 1623 queries used.
3 Correct 105 ms 7560 KB Ok! 1629 queries used.
4 Correct 102 ms 7636 KB Ok! 1641 queries used.
5 Correct 99 ms 7568 KB Ok! 1551 queries used.
6 Correct 97 ms 7676 KB Ok! 1567 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 7508 KB Ok! 1623 queries used.
2 Correct 104 ms 7560 KB Ok! 1619 queries used.