oj.uz

Submission #1025941

# Submission time Handle Problem Language Result Execution time Memory
1025941 2024-07-17T11:30:26 Z vjudge1 ICC (CEOI16_icc) C++14
0 / 100
 76 ms 604 KB 
#include <bits/stdc++.h>
#include <icc.h>

using namespace std;


int query(int size_a, int size_b, int a[], int b[]);

void setRoad(int a, int b);


void run(int N) {
    int T = N-1;
    vector<vector<int>>sets;
    for(int i=1; i<=N; ++i) {
        vector<int>tmp;
        tmp.push_back(i);
        sets.push_back(tmp);
    }
    while(T--) {
        int len = sets.size();
        while(len > 1) {
            int x = len / 2, cnt = 0;
            vector<int>v1, v2;
            for(int i=0; i<(int)sets.size(); i+=x) {
                for(int j = i; j < min(i+x, (int)sets.size()); ++j) {
                    if(cnt % 2) for(int k: sets[j]) v2.push_back(k);
                    else for(int k: sets[j]) v1.push_back(k);
                }
                ++cnt;
            }
            int arr1[v1.size()], arr2[v2.size()];
            for(int i=0; i<(int)v1.size(); ++i) arr1[i] = v1[i];
            for(int i=0; i<(int)v2.size(); ++i) arr2[i] = v2[i];
            int X = query((int)v1.size(), (int)v2.size(), arr1, arr2);
            if(!X) len /= 2;
            else {
                vector<int>V1, V2;
                for(int i=0; i<(int)sets.size(); i+=x) {
                    for(int j = i; j < min(i+x, (int)sets.size()); ++j) {
                        if(cnt%2) V2.push_back(j);
                        else V1.push_back(j);
                    }
                    ++cnt;
                }
                int l = 0, r = (int)V1.size() - 1;
                while(l < r) {
                    int m = (l+r)/2;
                    vector<int>nv;
                    for(int i=l; i<=m; ++i) {
                        for(int j: sets[V1[i]]) nv.push_back(j);
                    }
                    int siz = (int)nv.size(), arr_tmp[siz];
                    for(int i=0; i<siz; ++i) arr_tmp[i] = nv[i];
                    X = query(siz, (int)v2.size(), arr_tmp, arr2);
                    if(!X) l = m + 1;
                    else r = m;
                }
                int ans1 = V1[r];
                l = 0, r = (int)V2.size() - 1;
                while(l < r) {
                    int m = (l+r)/2;
                    vector<int>nv;
                    for(int i=l; i<=m; ++i) {
                        for(int j: sets[V2[i]]) nv.push_back(j);
                    }
                    int siz = (int)nv.size(), arr_tmp[siz];
                    for(int i=0; i<siz; ++i) arr_tmp[i] = nv[i];
                    X = query(siz, (int)v1.size(), arr_tmp, arr1);
                    if(!X) l = m + 1;
                    else r = m;
                }
                int ans2 = V2[r];
                l = 0, r = sets[ans1].size() - 1;
                int arr_tmp[sets[ans2].size()];
                for(int i=0; i<(int)sets[ans2].size(); ++i) arr_tmp[i] = sets[ans2][i];
                while(l < r) {
                    int m = (l+r)/2;
                    vector<int>nv;
                    for(int i=l; i<=m; ++i) nv.push_back(sets[ans1][i]);
                    int siz = nv.size(), arr_tmp2[siz];
                    for(int i=0; i<siz; ++i) arr_tmp2[i] = nv[i];
                    X = query(siz, (int)sets[ans2].size(), arr_tmp2, arr_tmp);
                    if(!X) l = m + 1;
                    else r = m;
                }
                int arr_tmp2[1] = {r};
                l = 0, r = (int)sets[ans2].size() - 1;
                while(l < r) {
                    int m = (l+r)/2;
                    vector<int>nv;
                    for(int i=l; i<=m; ++i) nv.push_back(sets[ans2][i]);
                    int siz = nv.size(), arr_tmp3[siz];
                    for(int i=0; i<siz; ++i) arr_tmp3[i] = nv[i];
                    X = query(siz, 1, arr_tmp3, arr_tmp2);
                    if(!X) l = m + 1;
                    else r = m;
                }
                setRoad(arr_tmp2[0], r);
                for(int x: sets[ans2]) sets[ans1].push_back(x);
                sets.erase(sets.begin() + ans2);
                break;
            }
        }
    }
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 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 1 ms 600 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 604 KB Wrong road!
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 44 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 35 ms 604 KB Not all edges were guessed!
2 Halted 0 ms 0 KB -