Submission #67161

#	Time	Username	Problem	Language	Result	Execution time	Memory
67161		polyfish	ICC (CEOI16_icc)	C++14	18 / 100	316 ms	836 KiB

icc

//I love armpit fetish

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

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 102;

int n, nSet, tmp_u[MAX_N], tmp_v[MAX_N];
bool a[MAX_N][MAX_N], in_set[MAX_N];
vector<int> S[MAX_N];

void make_set(int u) {
    S[nSet].push_back(u);
    in_set[u] = true;
    for (int i=1; i<=n; ++i) {
        if (a[u][i] && !in_set[i])
            make_set(i);
    }
}

vector<int> sub_vec(vector<int> A, int l, int r) {
    vector<int> res;
    for (int i=l; i<=r; ++i)
        res.push_back(A[i]);
    return res;
}

vector<int> join(vector<int> A) {
    vector<int> res;
    for (int i=0; i<A.size(); ++i)
        res.insert(res.end(), S[A[i]].begin(), S[A[i]].end());
    return res;
}

int get_query(vector<int> u, vector<int> v) {
    copy(u.begin(), u.end(), tmp_u);
    copy(v.begin(), v.end(), tmp_v);
    return query(u.size(), v.size(), tmp_u, tmp_v);
}

int bisect(vector<int> L, vector<int> R) {
    vector<int> L2 = join(L);
    int l = 0, r = R.size()-1, mid = (l + r) / 2;
    while (l!=mid && mid!=r) {
        if (get_query(L2, join(sub_vec(R, 0, mid))))
            r = mid;
        else
            l = mid;
        mid = (l + r) / 2;
    }
    for (int i=l; i<=r; ++i)
        if (get_query(L2, join(sub_vec(R, 0, i))))
            return R[i];
}

void find_new_connected_set(int &setID1, int &setID2) {
    vector<int> all;
    for (int i=1; i<=nSet; ++i)
        all.push_back(i);
    while (true) {
        random_shuffle(all.begin(), all.end());
        int mid = all.size() / 2 - 1;
        vector<int> L = sub_vec(all, 0, mid), R = sub_vec(all, mid+1, all.size()-1);
        if (get_query(join(L), join(R))) {
            setID1 = bisect(L, R);
            setID2 = bisect(R, L);
            return;
        }
    }
}

int find_new_edge(vector<int> L, vector<int> R) {
    int l = 0, r = R.size()-1, mid = (l + r) / 2;
    while (l!=mid && mid!=r) {
        if (get_query(L, sub_vec(R, 0, mid)))
            r = mid;
        else
            l = mid;
        mid = (l + r) / 2;
    }
    for (int i=l; i<=r; ++i)
        if (get_query(L, sub_vec(R, 0, i)))
            return R[i];
}

void run(int _n) {
    n = _n;
    srand(time(NULL));
    for (int j=1; j<n; ++j) {
        int setID1, setID2;
        memset(in_set, false, sizeof(in_set));
        for (int i=1; i<=nSet; ++i)
            S[i].clear();
        nSet = 0;
        for (int i=1; i<=n; ++i) {
            if (!in_set[i]) {
                ++nSet;
                make_set(i);
            }
        }
        find_new_connected_set(setID1, setID2);
        int u = find_new_edge(S[setID1], S[setID2]);
        int v = find_new_edge(S[setID2], S[setID1]);
        setRoad(u, v);
        a[u][v] = a[v][u] = true;
    }
}

//int main() {
//}

Compilation message (stderr)

icc.cpp: In function 'std::vector<int> join(std::vector<int>)':
icc.cpp:37:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0; i<A.size(); ++i)
                   ~^~~~~~~~~
icc.cpp: In function 'int bisect(std::vector<int>, std::vector<int>)':
icc.cpp:61:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
icc.cpp: In function 'int find_new_edge(std::vector<int>, std::vector<int>)':
icc.cpp:91:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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