제출 #141628

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
141628		lyc	ICC (CEOI16_icc)	C++14	90 / 100	152 ms	636 KiB

icc

#include "icc.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define SZ(x) (int)(x).size()
#define ALL(x) begin(x), end(x) 
#define REP(i, n) for (int i = 0; i < n; ++i) 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define RFOR(i, a, b) for (int i = a; i >= b; --i)

const int MAXN = 105;

vector<int> s[MAXN];
int p[MAXN];

void merge(int i, int j) {
    i = p[i]; j = p[j];
    if (SZ(s[i]) < SZ(s[j])) swap(i,j);
    for (auto c : s[j]) p[c] = i, s[i].push_back(c);
}

void run(int N) {
    FOR(i,1,N) p[i] = i, s[i].push_back(i);

    int a[N], b[N], ap, bp;
    FOR(e,1,N-1) {
        vector<int> comp;
        FOR(i,1,N) if (p[i] == i) comp.push_back(i);

        int sp = -1;
        FOR(x,0,(int)floor(log2(SZ(comp)))) {
            ap = bp = 0;
            FOR(i,0,SZ(comp)-1) {
                if (i&(1<<x)) { for (auto c : s[comp[i]]) a[ap++] = c; }
                else { for (auto c : s[comp[i]]) b[bp++] = c; }
            }

            //FOR(i,0,ap-1) { cout << a[i] << ' '; } cout << " AP " << ap << endl;
            //FOR(i,0,bp-1) { cout << b[i] << ' '; } cout << " BP " << bp << endl;

            if (ap != 0 and bp != 0 and query(ap,bp,a,b)) { sp = x; break; }
        }

        //FOR(x,0,6) { cout << diff[x] << " "; } cout << " SP " << sp << endl;

        ap = bp = 0;
        FOR(i,0,SZ(comp)-1) {
            if (i&(1<<sp)) { for (auto c : s[comp[i]]) a[ap++] = c; }
            else { for (auto c : s[comp[i]]) b[bp++] = c; }
        }

        assert(ap != 0 and bp != 0);

        int lo = 0, hi = ap;
        int a2[N+1];
        while (lo < hi) {
            int mid = (lo+hi)/2;
            FOR(i,lo,mid) a2[i-lo] = a[i];
            if (query(mid-lo+1,bp,a2,b)) hi = mid;
            else lo = mid+1;
        }
        int A = a[hi];

        a2[0] = A;
        
        lo = 0, hi = bp;
        int b2[N+1];
        while (lo < hi) {
            int mid = (lo+hi)/2;
            FOR(i,lo,mid) b2[i-lo] = b[i];
            if (query(1,mid-lo+1,a2,b2)) hi = mid;
            else lo = mid+1;
        }

        int B = b[hi];
        //cout << "A B " << A << " " << B << endl;
        setRoad(A,B);
        merge(A,B);
    }
}

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