oj.uz

Submission #67161

# Submission time Handle Problem Language Result Execution time Memory
67161 2018-08-13T12:41:19 Z polyfish ICC (CEOI16_icc) C++14
18 / 100
 316 ms 836 KB 
//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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 504 KB Ok! 187 queries used.
2 Correct 17 ms 612 KB Ok! 192 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 688 KB Ok! 961 queries used.
2 Correct 103 ms 704 KB Ok! 1098 queries used.
3 Correct 99 ms 704 KB Ok! 1124 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 279 ms 836 KB Too many queries! 2519 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 259 ms 836 KB Too many queries! 2632 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 293 ms 836 KB Too many queries! 2677 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 316 ms 836 KB Too many queries! 2714 out of 1625
2 Halted 0 ms 0 KB -