| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1028086 |
2024-07-19T13:15:32 Z |
serifefedartar |
ICC (CEOI16_icc) |
C++17 |
|
206 ms |
856 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define LOGN 20
const ll MOD = 1e9 + 7;
const ll MAXN = 105;
int par[MAXN], sz[MAXN], temp1[MAXN], temp2[MAXN];
int find(int node) {
if (node == par[node])
return node;
return par[node] = find(par[node]);
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return ;
if (sz[b] > sz[a])
swap(a, b);
sz[a] += sz[b];
par[b] = a;
}
int qry(int sz1, int sz2, vector<int> A, vector<int> B) {
for (int i = 0; i < sz1; i++)
temp1[i] = A[i];
for (int i = 0; i < sz2; i++)
temp2[i] = B[i];
return query(sz1, sz2, temp1, temp2);
}
bool control = true;
void dac(vector<vector<int>> A, vector<vector<int>> B) {
if (!control || A.size() == 0 || B.size() == 0)
return ;
vector<int> AA, BB;
for (auto u : A)
for (auto v : u)
AA.push_back(v);
for (auto u : B)
for (auto v : u)
BB.push_back(v);
random_shuffle(AA.begin(), AA.end());
random_shuffle(BB.begin(), BB.end());
if (qry(AA.size(), BB.size(), AA, BB)) {
while ((int)BB.size() > 1) {
vector<int> X, Y;
for (int i = 0; i < (int)BB.size() / 2; i++)
X.push_back(BB[i]);
for (int i = (int)BB.size() / 2; i < (int)BB.size(); i++)
Y.push_back(BB[i]);
if (qry(AA.size(), X.size(), AA, X))
BB = X;
else
BB = Y;
}
while ((int)AA.size() > 1) {
vector<int> X, Y;
for (int i = 0; i < (int)AA.size() / 2; i++)
X.push_back(AA[i]);
for (int i = (int)AA.size() / 2; i < (int)AA.size(); i++)
Y.push_back(AA[i]);
if (qry(X.size(), 1, X, BB))
AA = X;
else
AA = Y;
}
setRoad(BB[0], AA[0]);
unite(BB[0], AA[0]);
control = false;
} else {
vector<vector<int>> new_A1, new_A2;
vector<vector<int>> new_B1, new_B2;
for (int i = 0; i < (int)A.size() / 2; i++)
new_A1.push_back(A[i]);
for (int i = (int)A.size() / 2; i < (int)A.size(); i++)
new_A2.push_back(A[i]);
for (int i = 0; i < (int)B.size() / 2; i++)
new_B1.push_back(B[i]);
for (int i = (int)B.size() / 2; i < (int)B.size(); i++)
new_B2.push_back(B[i]);
random_shuffle(new_A1.begin(), new_A1.end());
random_shuffle(new_B1.begin(), new_B1.end());
dac(new_A1, new_A2);
dac(new_B1, new_B2);
}
}
int n;
void solve() {
map<int, vector<int>> mp;
for (int i = 1; i <= n; i++)
mp[find(i)].push_back(i);
vector<vector<int>> temp;
for (auto u : mp)
temp.push_back(u.s);
random_shuffle(temp.begin(), temp.end());
vector<vector<int>> A, B;
for (int i = 0; i < (int)temp.size() / 2; i++)
A.push_back(temp[i]);
for (int i = temp.size() / 2; i < (int)temp.size(); i++)
B.push_back(temp[i]);
control = true;
dac(A, B);
}
void run(int N) {
n = N;
for (int i = 1; i <= N; i++)
sz[i] = 1, par[i] = i;
for (int i = 1; i < N; i++)
solve();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
604 KB |
Ok! 108 queries used. |
| 2 |
Correct |
4 ms |
604 KB |
Ok! 105 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
33 ms |
656 KB |
Ok! 890 queries used. |
| 2 |
Correct |
57 ms |
604 KB |
Ok! 1332 queries used. |
| 3 |
Correct |
54 ms |
600 KB |
Ok! 1343 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
206 ms |
600 KB |
Number of queries more than 4500 out of 2250 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
180 ms |
856 KB |
Number of queries more than 4000 out of 2000 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
166 ms |
600 KB |
Number of queries more than 3550 out of 1775 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
152 ms |
600 KB |
Number of queries more than 3250 out of 1625 |
| 2 |
Halted |
0 ms |
0 KB |
- |
