oj.uz

답안 #141619

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
141619 2019-08-08T14:37:17 Z lyc CEOI16_icc (CEOI16_icc) C++14
61 / 100
 193 ms 692 KB 
#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) {
        bool diff[7] = {0};
        int sp = -1;
        FOR(x,0,6) {
            ap = bp = 0;
            FOR(i,1,N) if (p[i] == i) {
                if (i&(1<<x)) { for (auto c : s[i]) a[ap++] = c; }
                else { for (auto c : s[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) diff[x] = 0;
            else if (bp == 0) diff[x] = 0;
            else diff[x] = query(ap,bp,a,b);
            //cout << diff[x] << endl << endl;;
            if (diff[x]) sp = x;
        }

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

        ap = bp = 0;
        FOR(i,1,N) if (p[i] == i) {
            if (i&(1<<sp)) { for (auto c : s[i]) a[ap++] = c; }
            else { for (auto c : s[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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 504 KB Ok! 141 queries used.
2 Correct 11 ms 504 KB Ok! 143 queries used.

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 54 ms 504 KB Ok! 743 queries used.
2 Correct 53 ms 596 KB Ok! 738 queries used.
3 Correct 53 ms 504 KB Ok! 744 queries used.

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 164 ms 556 KB Ok! 1813 queries used.
2 Correct 164 ms 596 KB Ok! 1754 queries used.
3 Correct 161 ms 504 KB Ok! 1810 queries used.
4 Correct 167 ms 564 KB Ok! 1798 queries used.

Subtask #4
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 163 ms 552 KB Ok! 1788 queries used.
2 Correct 193 ms 504 KB Ok! 1796 queries used.
3 Correct 168 ms 504 KB Ok! 1825 queries used.
4 Correct 167 ms 692 KB Ok! 1798 queries used.

Subtask #5
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 170 ms 556 KB Too many queries! 1813 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 169 ms 556 KB Too many queries! 1818 out of 1625
2 Halted 0 ms 0 KB -