oj.uz

Submission #67160

# Submission time Handle Problem Language Result Execution time Memory
67160 2018-08-13T12:21:40 Z polyfish ICC (CEOI16_icc) C++14
18 / 100
 443 ms 960 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];
}

bool find_new_connected_set(vector<int> all, int &setID1, int &setID2) {
    if (all.size()<=1)
        return false;
    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);
    int tmp = get_query(join(L), join(R));
    if (tmp==0) {
        if (rand()%2==0) {
            if (find_new_connected_set(L, setID1, setID2))
                return true;
            return find_new_connected_set(R, setID1, setID2);
        }
        if (find_new_connected_set(R, setID1, setID2))
            return true;
        return find_new_connected_set(L, setID1, setID2);
    }
    setID1 = bisect(L, R);
    setID2 = bisect(R, L);
    return true;
}

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 i=1; i<n; ++i) {
        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);
            }
        }
        vector<int> all;
        for (int i=1; i<=nSet; ++i)
            all.push_back(i);
        int p[] = {7};
        int q[] = {3};
        //debug(query(1, 1, p, q));
        find_new_connected_set(all, 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 'void run(int)':
icc.cpp:117:13: warning: unused variable 'p' [-Wunused-variable]
         int p[] = {7};
             ^
icc.cpp:118:13: warning: unused variable 'q' [-Wunused-variable]
         int q[] = {3};
             ^
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:97: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 18 ms 504 KB Ok! 187 queries used.
2 Correct 15 ms 652 KB Ok! 177 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 672 KB Ok! 1271 queries used.
2 Correct 125 ms 832 KB Ok! 1535 queries used.
3 Correct 123 ms 960 KB Ok! 1555 queries used.

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 960 KB Number of queries more than 4500 out of 2250
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 387 ms 960 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 329 ms 960 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 306 ms 960 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -