| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605108 |
2022-07-25T13:05:32 Z |
pliam |
ICC (CEOI16_icc) |
C++14 |
|
145 ms |
596 KB |
#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 105
int par[MAXN],height[MAXN];
vector<int> elems[MAXN];
vector<int> ccs;
int find_set(int v){
if(par[v]==v) return v;
else return par[v]=find_set(par[v]);
}
void union_sets(int a,int b){
a=find_set(a);
b=find_set(b);
if(a==b) return;
if(height[a]<height[b]) swap(a,b);
par[b]=a;
if(height[a]==height[b]) height[a]++;
for(int v:elems[b]){
elems[a].push_back(v);
}
}
vector<pair<vector<int>,vector<int>>> curr,case1,case2;
bool same_set;
bool all_one;
vector<int> white;
vector<int> black;
int query_case(vector<pair<vector<int>,vector<int>>> cas){
white.clear();
black.clear();
for(auto p:cas){
for(int c:p.first){
for(int i:elems[c]){
white.push_back(i);
}
}for(int c:p.second){
for(int i:elems[c]){
black.push_back(i);
}
}
}
int arr_white[white.size()];
for(int i=0;i<white.size();i++){
arr_white[i]=white[i];
}
int arr_black[black.size()];
for(int i=0;i<black.size();i++){
arr_black[i]=black[i];
}
return query(white.size(),black.size(),arr_white,arr_black);
}
int query_sets(){
int arr_white[white.size()];
for(int i=0;i<white.size();i++){
arr_white[i]=white[i];
}
int arr_black[black.size()];
for(int i=0;i<black.size();i++){
arr_black[i]=black[i];
}
return query(white.size(),black.size(),arr_white,arr_black);
}
void construct_cases_same_set(){
case1.clear();
case2.clear();
for(auto p:curr){
if(p.first.size()==1) continue;
//else cut it in half
vector<int> firsth,secondh;
int n=p.first.size();
int mid=n/2;
for(int i=0;i<mid;i++){
firsth.push_back(p.first[i]);
}for(int i=mid;i<n;i++){
secondh.push_back(p.first[i]);
}
case1.push_back({firsth,secondh});
case2.push_back({firsth,firsth});
case2.push_back({secondh,secondh});
}
}
void construct_cases_diff_set(){
all_one=true;
case1.clear();
case2.clear();
for(auto p:curr){
vector<int> seta=p.first;
vector<int> setb=p.second;
//else cut them in half
vector<int> set1,set2,set3,set4;
int n=seta.size();
int m=setb.size();
int mid1=n/2;
int mid2=m/2;
for(int i=0;i<mid1;i++){
set1.push_back(seta[i]);
}for(int i=mid1;i<n;i++){
set2.push_back(seta[i]);
}
for(int i=0;i<mid2;i++){
set3.push_back(setb[i]);
}for(int i=mid2;i<m;i++){
set4.push_back(setb[i]);
}
if(n==m&&n==1){
case1.push_back({set2,set4});
case2.push_back({set2,set4});
}else if(n==1){
case1.push_back({set2,set3});
case2.push_back({set2,set4});
all_one=false;
}else if(m==1){
case1.push_back({set1,set4});
case2.push_back({set2,set4});
all_one=false;
}else{
case1.push_back({set1,set3}); case1.push_back({set4,set2});
case2.push_back({set1,set4}); case2.push_back({set3,set2});
all_one=false;
}
}
}
void construct_cases_cc(){
case1.clear();
case2.clear();
int n=curr.size();
int mid=n/2;
for(int i=0;i<mid;i++){
case1.push_back({curr[i].first,curr[i].second});
}for(int i=mid;i<n;i++){
case2.push_back({curr[i].first,curr[i].second});
}
}
bool check_a(int a,int k){
white.clear();
for(int i=0;i<=k;i++){
white.push_back(elems[a][i]);
}
return query_sets();
}
bool check_b(int b,int k){
black.clear();
for(int i=0;i<=k;i++){
black.push_back(elems[b][i]);
}
return query_sets();
}
pair<int,int> find_edge(int N){
same_set=true;
ccs.clear();
for(int i=1;i<=N;i++){
if(par[i]==i) ccs.push_back(i);
}
curr={{ccs,ccs}};
while(same_set){
construct_cases_same_set();
int ansq=query_case(case1);
if(ansq){
same_set=false;
curr=case1;
all_one=false;
}else{
curr=case2;
}
}
//now we go to the second part
while(1){
construct_cases_diff_set();
if(all_one) break;
int ansq=query_case(case1);
if(ansq)curr=case1;
else curr=case2;
}
//now to the third part where we have pairs of cc's
while(curr.size()>=2){
construct_cases_cc();
int ansq=query_case(case1);
if(ansq) curr=case1;
else curr=case2;
}
//now we have pair of cc's
int a=curr[0].first[0];
int b=curr[0].second[0];
black=elems[b];
int k=elems[a].size()-1;
for(int bh=elems[a].size();bh>0;bh/=2){
while(k-bh>=0&&check_a(a,k-bh)) k-=bh;
}
int edgea=elems[a][k];
white={edgea};
k=elems[b].size()-1;
for(int bh=elems[b].size();bh>0;bh/=2){
while(k-bh>=0&&check_b(b,k-bh)) k-=bh;
}
int edgeb=elems[b][k];
return {edgea,edgeb};
}
void run(int N){
for(int i=1;i<=N;i++){
par[i]=i;
elems[i]={i};
}
for(int i=1;i<=N-1;i++){
pair<int,int> edge=find_edge(N);
union_sets(edge.first,edge.second);
setRoad(edge.first,edge.second);
}
}
Compilation message
icc.cpp: In function 'int query_case(std::vector<std::pair<std::vector<int>, std::vector<int> > >)':
icc.cpp:49:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int i=0;i<white.size();i++){
| ~^~~~~~~~~~~~~
icc.cpp:53:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
53 | for(int i=0;i<black.size();i++){
| ~^~~~~~~~~~~~~
icc.cpp: In function 'int query_sets()':
icc.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
61 | for(int i=0;i<white.size();i++){
| ~^~~~~~~~~~~~~
icc.cpp:65:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<black.size();i++){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
596 KB |
Ok! 116 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 121 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
34 ms |
520 KB |
Ok! 668 queries used. |
| 2 |
Correct |
31 ms |
524 KB |
Ok! 586 queries used. |
| 3 |
Correct |
31 ms |
528 KB |
Ok! 586 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
145 ms |
524 KB |
Ok! 1634 queries used. |
| 2 |
Correct |
104 ms |
536 KB |
Ok! 1436 queries used. |
| 3 |
Correct |
118 ms |
536 KB |
Ok! 1564 queries used. |
| 4 |
Correct |
136 ms |
536 KB |
Ok! 1631 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
125 ms |
596 KB |
Ok! 1569 queries used. |
| 2 |
Correct |
109 ms |
536 KB |
Ok! 1591 queries used. |
| 3 |
Correct |
113 ms |
588 KB |
Ok! 1467 queries used. |
| 4 |
Correct |
109 ms |
468 KB |
Ok! 1638 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
548 KB |
Ok! 1499 queries used. |
| 2 |
Correct |
108 ms |
544 KB |
Ok! 1441 queries used. |
| 3 |
Correct |
107 ms |
548 KB |
Ok! 1480 queries used. |
| 4 |
Correct |
105 ms |
544 KB |
Ok! 1500 queries used. |
| 5 |
Correct |
137 ms |
536 KB |
Ok! 1618 queries used. |
| 6 |
Correct |
137 ms |
524 KB |
Ok! 1569 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
101 ms |
536 KB |
Ok! 1472 queries used. |
| 2 |
Correct |
96 ms |
548 KB |
Ok! 1436 queries used. |
