Submission #373338

#	Time	Username	Problem	Language	Result	Execution time	Memory
373338		ijxjdjd	ICC (CEOI16_icc)	C++14	61 / 100	221 ms	748 KiB

icc

#include <bits/stdc++.h>
#include "icc.h"
#define FR(i, N) for (int i = 0; i < int(N); i++)
#define all(x) begin(x), end(x)

using namespace std;

using ll = long long;

const int MAXN = 105;
int component[MAXN];
vector<vector<int>> comps;
vector<int> active;
bool query(vector<int> a, vector<int> b) {
    int A[a.size()];
    int B[b.size()];
    FR(i, a.size()) {
        A[i] = a[i]+1;
    }
    FR(i, b.size()) {
        B[i] = b[i]+1;
    }
    return query(a.size(), b.size(), A, B);
}
void merge(int u, int v) {
    int del = component[u];
    active.erase(find(all(active), del));
    for (int a : comps[del]) {
        component[a] = component[v];
        comps[component[v]].push_back(a);
    }
}
void run(int N) {
    comps.resize(N);
    FR(i, N) {
        comps[i].push_back(i);
        component[i] = i;
        active.push_back(i);
    }
    for (int c = N; c >= 2; c--) {
        int ct = 0;
        srand(time(NULL));
        while (true) {
            ct++;
            vector<int> A;
            vector<int> B;
            for (int i = 0; i < c; i++) {
                if (rand()%2) {
                    A.insert(A.end(), all(comps[active[i]]));
                }
                else {
                    B.insert(B.end(), all(comps[active[i]]));
                }
            }
            if (A.size() != 0 && B.size() != 0) {
                if (query(A, B)) {
                    int high = A.size()-1;
                    int low = 0;
                    int u, v;
                    while (low < high) {
                        int mid = (low + high)/2;
                        vector<int> next;
                        next.insert(next.end(), A.begin(), A.begin()+mid+1);
                        if (query(next, B)) {
                            high = mid;
                        }
                        else {
                            low = mid+1;
                        }
                    }
                    u = A[high];
                    low = 0;
                    high = B.size()-1;
                    while (low < high) {
                        int mid = (low + high)/2;
                        vector<int> next;
                        next.insert(next.end(), B.begin(), B.begin()+mid+1);
                        if (query(next, A)) {
                            high = mid;
                        }
                        else {
                            low = mid+1;
                        }
                    }
                    v = B[high];
                    setRoad(u+1, v+1);
                    merge(u, v);
                    break;
                }
            }
        }
//        if (ct >= 18) {
//            return;
//        }
    }
}

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