oj.uz

Submission #141628

# Submission time Handle Problem Language Result Execution time Memory
141628 2019-08-08T14:53:06 Z lyc ICC (CEOI16_icc) C++14
90 / 100
 152 ms 636 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) {
        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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Ok! 104 queries used.
2 Correct 9 ms 504 KB Ok! 109 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 504 KB Ok! 545 queries used.
2 Correct 48 ms 504 KB Ok! 669 queries used.
3 Correct 49 ms 504 KB Ok! 672 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 560 KB Ok! 1440 queries used.
2 Correct 149 ms 564 KB Ok! 1647 queries used.
3 Correct 143 ms 636 KB Ok! 1597 queries used.
4 Correct 144 ms 504 KB Ok! 1533 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 636 KB Ok! 1588 queries used.
2 Correct 143 ms 560 KB Ok! 1552 queries used.
3 Correct 148 ms 504 KB Ok! 1643 queries used.
4 Correct 143 ms 596 KB Ok! 1533 queries used.

Subtask #5
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 464 KB Ok! 1651 queries used.
2 Correct 147 ms 504 KB Ok! 1643 queries used.
3 Correct 149 ms 600 KB Ok! 1643 queries used.
4 Correct 151 ms 564 KB Ok! 1653 queries used.
5 Correct 132 ms 504 KB Ok! 1404 queries used.
6 Correct 148 ms 508 KB Ok! 1542 queries used.

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 152 ms 572 KB Too many queries! 1672 out of 1625
2 Halted 0 ms 0 KB -