| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 869513 |
2023-11-04T15:17:13 Z |
Andrey |
ICC (CEOI16_icc) |
C++14 |
|
92 ms |
936 KB |
#include "icc.h"
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> dsu(10001);
vector<int> haha[1001];
int bin(int a, int b) {
int l = 0,r = haha[a].size()-1;
int yay[haha[b].size()];
for(int i = 0; i < haha[b].size(); i++) {
yay[i] = haha[b][i];
}
while(l < r) {
int m = (l+r)/2;
int wut[m-l+1];
for(int i = l; i <= m; i++) {
wut[i-l] = haha[a][i];
}
if(query(haha[b].size(),m-l+1,yay,wut)) {
r = m;
}
else {
l = m+1;
}
}
return haha[a][l];
}
int wow(vector<int> a, vector<int> b) {
vector<int> wut(0);
vector<int> yay(0);
for(int i = 0; i < a.size(); i++) {
for(int j = 0; j < haha[a[i]].size(); j++) {
wut.push_back(haha[a[i]][j]);
}
}
for(int i = 0; i < b.size(); i++) {
for(int j = 0; j < haha[b[i]].size(); j++) {
yay.push_back(haha[b[i]][j]);
}
}
int c[wut.size()],d[yay.size()];
for(int i = 0; i < wut.size(); i++) {
c[i] = wut[i];
}
for(int i = 0; i < yay.size(); i++) {
d[i] = yay[i];
}
return query(wut.size(),yay.size(),c,d);
}
pair<int,int> dude(int br) {
vector<int> a(0);
vector<int> b(0);
bool yay[20];
int p = -1,x = 0,y = 0;
for(int i = 0; (1 << i) <= br; i++) {
a.clear();
b.clear();
for(int j = 0; j < br; j++) {
if((1 << i)&j) {
a.push_back(j);
}
else {
b.push_back(j);
}
}
yay[i] = wow(a,b);
if(p == -1 && yay[i]) {
p = i;
}
}
for(int i = 0; (1 << i) <= br; i++) {
if(i != p) {
a.clear();
b.clear();
for(int j = 0; j < br; j++) {
if(((1 << i)&j) && ((1 << p)&j)) {
a.push_back(j);
}
else {
b.push_back(j);
}
}
bool yeah = wow(a,b);
if(yeah) {
x+=(1 << i);
}
if(yeah != yay[i]) {
y+=(1 << i);
}
}
else {
x+=(1 << p);
}
}
return {x,y};
}
int calc(int a) {
int c = a;
while(dsu[c] != c) {
c = dsu[c];
}
return c;
}
void edge(int a, int b) {
a = calc(a),b = calc(b);
dsu[a] = b;
}
void run(int N) {
n = N;
for(int i = 1; i <= n; i++) {
dsu[i] = i;
}
for(int i = 0; i < n-1; i++) {
int a = -1,b = -1,br = 0;
vector<bool> yay(n+1,true);
for(int j = 0; j < n; j++) {
haha[j].clear();
for(int y = 1; y <= n; y++) {
if(yay[y]) {
if(haha[j].empty() || calc(haha[j][0]) == calc(y)) {
haha[j].push_back(y);
yay[y] = false;
}
}
}
if(haha[j].empty()) {
break;
}
br++;
}
pair<int,int> q = dude(br);
a = bin(q.first,q.second);
b = bin(q.second,q.first);
edge(a,b);
setRoad(a,b);
}
}
Compilation message
icc.cpp: In function 'int bin(int, int)':
icc.cpp:12:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
12 | for(int i = 0; i < haha[b].size(); i++) {
| ~~^~~~~~~~~~~~~~~~
icc.cpp: In function 'int wow(std::vector<int>, std::vector<int>)':
icc.cpp:34:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i = 0; i < a.size(); i++) {
| ~~^~~~~~~~~~
icc.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
35 | for(int j = 0; j < haha[a[i]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~
icc.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | for(int i = 0; i < b.size(); i++) {
| ~~^~~~~~~~~~
icc.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for(int j = 0; j < haha[b[i]].size(); j++) {
| ~~^~~~~~~~~~~~~~~~~~~
icc.cpp:45:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
45 | for(int i = 0; i < wut.size(); i++) {
| ~~^~~~~~~~~~~~
icc.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | for(int i = 0; i < yay.size(); i++) {
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
600 KB |
Ok! 123 queries used. |
| 2 |
Correct |
5 ms |
604 KB |
Ok! 122 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
27 ms |
604 KB |
Ok! 657 queries used. |
| 2 |
Correct |
24 ms |
604 KB |
Ok! 625 queries used. |
| 3 |
Correct |
29 ms |
600 KB |
Ok! 634 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
600 KB |
Ok! 1613 queries used. |
| 2 |
Correct |
74 ms |
696 KB |
Ok! 1568 queries used. |
| 3 |
Correct |
79 ms |
688 KB |
Ok! 1621 queries used. |
| 4 |
Correct |
81 ms |
604 KB |
Ok! 1596 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
92 ms |
704 KB |
Ok! 1587 queries used. |
| 2 |
Correct |
79 ms |
600 KB |
Ok! 1584 queries used. |
| 3 |
Correct |
82 ms |
704 KB |
Ok! 1599 queries used. |
| 4 |
Correct |
90 ms |
680 KB |
Ok! 1600 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
600 KB |
Ok! 1568 queries used. |
| 2 |
Correct |
76 ms |
936 KB |
Ok! 1568 queries used. |
| 3 |
Correct |
80 ms |
688 KB |
Ok! 1599 queries used. |
| 4 |
Correct |
77 ms |
684 KB |
Ok! 1599 queries used. |
| 5 |
Correct |
84 ms |
604 KB |
Ok! 1611 queries used. |
| 6 |
Correct |
92 ms |
684 KB |
Ok! 1614 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
88 ms |
684 KB |
Ok! 1599 queries used. |
| 2 |
Correct |
78 ms |
604 KB |
Ok! 1568 queries used. |
