# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
1028776 |
2024-07-20T08:32:22 Z |
serifefedartar |
ICC (CEOI16_icc) |
C++17 |
|
103 ms |
672 KB |
#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
mt19937 mt(chrono::system_clock::now().time_since_epoch().count());
#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);
}
int n;
void match(vector<vector<int>> arr) {
while (true) {
shuffle(arr.begin(), arr.end(), mt);
for (int rep = 0; rep < 10; rep++) {
vector<int> A, B;
for (int i = 0; i < arr.size(); i++) {
if (i & (1<<rep)) {
for (auto u : arr[i])
A.push_back(u);
} else {
for (auto u : arr[i])
B.push_back(u);
}
}
if (qry(A.size(), B.size(), A, B)) {
shuffle(A.begin(), A.end(), mt);
shuffle(B.begin(), B.end(), mt);
while ((int)B.size() > 1) {
vector<int> X, Y;
for (int i = 0; i < (int)B.size() / 2; i++)
X.push_back(B[i]);
for (int i = (int)B.size() / 2; i < (int)B.size(); i++)
Y.push_back(B[i]);
if (qry(A.size(), X.size(), A, X))
B = X;
else
B = Y;
}
while ((int)A.size() > 1) {
vector<int> X, Y;
for (int i = 0; i < (int)A.size() / 2; i++)
X.push_back(A[i]);
for (int i = (int)A.size() / 2; i < (int)A.size(); i++)
Y.push_back(A[i]);
if (qry(X.size(), 1, X, B))
A = X;
else
A = Y;
}
setRoad(B[0], A[0]);
unite(B[0], A[0]);
return ;
}
}
}
}
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);
match(temp);
}
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();
}
Compilation message
icc.cpp: In function 'void match(std::vector<std::vector<int> >)':
icc.cpp:47:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for (int i = 0; i < arr.size(); i++) {
| ~~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
600 KB |
Ok! 98 queries used. |
2 |
Correct |
4 ms |
640 KB |
Ok! 96 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
604 KB |
Ok! 541 queries used. |
2 |
Correct |
26 ms |
600 KB |
Ok! 684 queries used. |
3 |
Correct |
26 ms |
600 KB |
Ok! 661 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
71 ms |
600 KB |
Ok! 1438 queries used. |
2 |
Correct |
80 ms |
604 KB |
Ok! 1630 queries used. |
3 |
Correct |
73 ms |
672 KB |
Ok! 1542 queries used. |
4 |
Correct |
90 ms |
604 KB |
Ok! 1517 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
73 ms |
600 KB |
Ok! 1543 queries used. |
2 |
Correct |
67 ms |
644 KB |
Ok! 1522 queries used. |
3 |
Correct |
79 ms |
604 KB |
Ok! 1627 queries used. |
4 |
Correct |
73 ms |
604 KB |
Ok! 1482 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
78 ms |
600 KB |
Ok! 1613 queries used. |
2 |
Correct |
103 ms |
656 KB |
Ok! 1642 queries used. |
3 |
Correct |
100 ms |
604 KB |
Ok! 1653 queries used. |
4 |
Correct |
78 ms |
664 KB |
Ok! 1620 queries used. |
5 |
Correct |
71 ms |
644 KB |
Ok! 1498 queries used. |
6 |
Correct |
77 ms |
604 KB |
Ok! 1553 queries used. |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
77 ms |
604 KB |
Ok! 1620 queries used. |
2 |
Incorrect |
81 ms |
660 KB |
Too many queries! 1652 out of 1625 |
3 |
Halted |
0 ms |
0 KB |
- |