oj.uz

Submission #585645

# Submission time Handle Problem Language Result Execution time Memory
585645 2022-06-29T07:14:04 Z 반딧불(#8385) ICC (CEOI16_icc) C++14
100 / 100
 133 ms 588 KB 
#include "icc.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int qa[105], qb[105];

int query(vector<int> a, vector<int> b){
    if(a.empty() || b.empty()) return false;
    for(auto A: a) for(auto B: b) assert(A!=B);

    for(int i=0; i<(int)a.size(); i++) qa[i] = a[i];
    for(int i=0; i<(int)b.size(); i++) qb[i] = b[i];
    return query(a.size(), b.size(), qa, qb);
}

struct unionFind{
    int par[105];
    void init(int n){
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int x){
        if(x==par[x]) return x;
        return par[x] = find(par[x]);
    }

    void merge(int x, int y){
        x = find(x), y = find(y);
        par[x] = y;
    }
} dsu;

int n;

void run(int N){
    n = N;
    dsu.init(n);
    for(int cnt=1; cnt<n; cnt++){
        /// �׷� ����
        vector<vector<int> > vec;
        for(int i=1; i<=n; i++){
            if(dsu.find(i) != i) continue;
            vec.push_back(vector<int>(0));
            for(int j=1; j<=n; j++){
                if(dsu.find(j) == i) vec.back().push_back(j);
            }
        }

        int offset = 0;
        int groupCnt = (int)vec.size();
        { /// �� �׷��� XOR �� ã��
            for(int d=0; d<7; d++){
                vector<int> ga, gb;
                vector<int> va, vb;
                for(int i=0; i<groupCnt; i++){
                    if((i>>d)&1) ga.push_back(i);
                    else gb.push_back(i);
                }
                if(ga.empty() || gb.empty()) continue;
                for(auto x: ga) for(auto y: vec[x]) va.push_back(y);
                for(auto x: gb) for(auto y: vec[x]) vb.push_back(y);
                if(query(va, vb)) offset |= (1<<d);
            }
        }

        int gx, gy;
        { /// XOR�� �� ��, �� �׷� Ȯ������
            vector<int> gVec;
            for(int i=0; i<groupCnt; i++){
                if((i^offset) < groupCnt && (i^offset) > i) gVec.push_back(i);
            }
            int L = 0, R = (int)gVec.size()-2, ANS = (int)gVec.size()-1;
            while(L <= R){
                int MID = (L+R)/2;
                vector<int> qa, qb;
                for(int i=0; i<=MID; i++) for(int j: vec[gVec[i]]) qa.push_back(j);
                for(int i=0; i<=MID; i++) for(int j: vec[gVec[i]^offset]) qb.push_back(j);
                if(query(qa, qb)) ANS = MID, R = MID-1;
                else L = MID+1;
            }
            gx = gVec[ANS], gy = gx^offset;
        }

        vector<int> vx = vec[gx], vy = vec[gy];
        int px, py;
        {
            int L = 0, R = (int)vx.size()-2, ANS = R+1;
            while(L <= R){
                int MID = (L+R)/2;
                vector<int> qa;
                for(int i=0; i<=MID; i++) qa.push_back(vx[i]);
                if(query(qa, vy)) ANS = MID, R = MID-1;
                else L = MID+1;
            }
            px = vx[ANS];
        }
        {
            int L = 0, R = (int)vy.size()-2, ANS = R+1;
            while(L<=R){
                int MID = (L+R)/2;
                vector<int> qb;
                for(int i=0; i<=MID; i++) qb.push_back(vy[i]);
                if(query(vector<int>(1, px), qb)) ANS = MID, R = MID-1;
                else L = MID+1;
            }
            py = vy[ANS];
        }

        setRoad(px, py);
        dsu.merge(px, py);
    }
}

Subtask #1
7.0 / 7.0

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

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 468 KB Ok! 603 queries used.
2 Correct 31 ms 508 KB Ok! 571 queries used.
3 Correct 31 ms 468 KB Ok! 609 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 500 KB Ok! 1520 queries used.
2 Correct 97 ms 492 KB Ok! 1493 queries used.
3 Correct 100 ms 508 KB Ok! 1493 queries used.
4 Correct 113 ms 500 KB Ok! 1480 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 468 KB Ok! 1470 queries used.
2 Correct 133 ms 492 KB Ok! 1468 queries used.
3 Correct 104 ms 588 KB Ok! 1493 queries used.
4 Correct 102 ms 500 KB Ok! 1507 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 504 KB Ok! 1487 queries used.
2 Correct 101 ms 492 KB Ok! 1492 queries used.
3 Correct 101 ms 496 KB Ok! 1490 queries used.
4 Correct 106 ms 496 KB Ok! 1487 queries used.
5 Correct 99 ms 468 KB Ok! 1479 queries used.
6 Correct 106 ms 500 KB Ok! 1467 queries used.

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 496 KB Ok! 1492 queries used.
2 Correct 105 ms 492 KB Ok! 1493 queries used.