oj.uz

Submission #373338

# Submission time Handle Problem Language Result Execution time Memory
373338 2021-03-04T07:27:14 Z ijxjdjd ICC (CEOI16_icc) C++14
61 / 100
 221 ms 748 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 492 KB Ok! 102 queries used.
2 Correct 8 ms 620 KB Ok! 103 queries used.

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 492 KB Ok! 544 queries used.
2 Correct 62 ms 620 KB Ok! 868 queries used.
3 Correct 56 ms 492 KB Ok! 781 queries used.

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 153 ms 620 KB Ok! 1489 queries used.
2 Correct 221 ms 620 KB Ok! 2131 queries used.
3 Correct 169 ms 620 KB Ok! 1746 queries used.
4 Correct 172 ms 748 KB Ok! 1673 queries used.

Subtask #4
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 620 KB Ok! 1665 queries used.
2 Correct 161 ms 620 KB Ok! 1655 queries used.
3 Correct 176 ms 620 KB Ok! 1832 queries used.
4 Correct 163 ms 620 KB Ok! 1591 queries used.

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 620 KB Too many queries! 1880 out of 1775
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 193 ms 492 KB Too many queries! 1935 out of 1625
2 Halted 0 ms 0 KB -