oj.uz

Submission #141615

# Submission time Handle Problem Language Result Execution time Memory
141615 2019-08-08T14:32:40 Z lyc ICC (CEOI16_icc) C++14
0 / 100
 51 ms 632 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) {
    if (SZ(s[i]) < SZ(s[j])) swap(i,j);
    for (auto c : s[j]) p[c] = p[i], s[p[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
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 508 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 22 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 51 ms 632 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 38 ms 504 KB The query sets must be disjoint
2 Halted 0 ms 0 KB -