| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 605039 |
2022-07-25T12:28:43 Z |
Theo830 |
ICC (CEOI16_icc) |
C++17 |
|
198 ms |
1076 KB |
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///CEOI 2016 day 1
#include "icc.h"
/*
int query(int size_a, int size_b, int a[], int b[]){
cout<<size_a<<" : ";
f(i,0,size_a){
cout<<a[i]<<" ";
}
cout<<"\n";
cout<<size_b<<" : ";
f(i,0,size_b){
cout<<b[i]<<" ";
}
cout<<"\n";
ll v;
cin>>v;
return v;
}
*/
ll par[1005];
ll find_par(ll a){
if(par[a] == a){
return a;
}
return par[a] = find_par(par[a]);
}
void enose(ll a,ll b){
a = find_par(a);
b = find_par(b);
par[a] = b;
}
void run(int N){
ll n = N;
f(i,0,n+5){
par[i] = i;
}
while(1){
ll a = -1,b = -1;
set<ll>com;
vll exo[n+5];
vll arr;
f(i,1,n+1){
exo[find_par(i)].pb(i);
com.insert(find_par(i));
}
for(auto x:com){
arr.pb(x);
}
vll AA,BB;
set<ll>lathos[n+5];
while(1){
vll A[2];
f(i,0,arr.size()){
A[i % 2].pb(arr[i]);
}
arr = A[0];
for(auto x:A[1]){
arr.pb(x);
}
vll nA,nB;
for(auto x:A[0]){
for(auto y:exo[x]){
nA.pb(y);
}
}
for(auto x:A[1]){
for(auto y:exo[x]){
nB.pb(y);
}
}
ll sa = nA.size();
ll sb = nB.size();
ll aa[sa],bb[sb];
f(i,0,sa){
aa[i] = nA[i];
}
f(i,0,sb){
bb[i] = nB[i];
}
if(query(sa,sb,aa,bb) == 1){
AA = nA;
BB = nB;
break;
}
else{
for(auto x:A[0]){
for(auto y:A[1]){
lathos[x].insert(y);
lathos[y].insert(x);
}
}
}
}
ll l = 0,r = AA.size() - 1;
ll pos = r + 1;
while(l <= r){
ll mid = (l+r)/2;
ll sa = AA.size();
ll sb = BB.size();
ll aa[mid+1],bb[sb];
f(i,0,mid+1){
aa[i] = AA[i];
}
f(i,0,sb){
bb[i] = BB[i];
}
if(query(mid+1,sb,aa,bb) == 1){
r = mid - 1;
pos = min(pos,mid);
}
else{
l = mid + 1;
}
}
a = AA[pos];
vll C;
for(auto x:BB){
if(!lathos[a].count(x)){
C.pb(x);
}
}
BB = C;
l = 0,r = BB.size() - 2;
pos = r + 1;
while(l <= r){
ll mid = (l+r)/2;
ll sa = AA.size();
ll sb = BB.size();
ll aa[sa],bb[mid+1];
f(i,0,sa){
aa[i] = AA[i];
}
f(i,0,mid+1){
bb[i] = BB[i];
}
if(query(sa,mid+1,aa,bb) == 1){
r = mid - 1;
pos = min(pos,mid);
}
else{
l = mid + 1;
}
}
b = BB[pos];
setRoad(a,b);
enose(a,b);
}
}
/*
int main(){
run(4);
}
*/
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:8:33: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
8 | #define f(i,a,b) for(ll i = a;i < b;i++)
......
76 | f(i,0,arr.size()){
| ~~~~~~~~~~~~~~
icc.cpp:76:13: note: in expansion of macro 'f'
76 | f(i,0,arr.size()){
| ^
icc.cpp:121:16: warning: unused variable 'sa' [-Wunused-variable]
121 | ll sa = AA.size();
| ^~
icc.cpp:151:16: warning: unused variable 'sb' [-Wunused-variable]
151 | ll sb = BB.size();
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
468 KB |
Ok! 100 queries used. |
| 2 |
Correct |
6 ms |
468 KB |
Ok! 102 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
30 ms |
468 KB |
Ok! 534 queries used. |
| 2 |
Correct |
39 ms |
596 KB |
Ok! 645 queries used. |
| 3 |
Correct |
38 ms |
604 KB |
Ok! 640 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
140 ms |
936 KB |
Ok! 1369 queries used. |
| 2 |
Correct |
198 ms |
980 KB |
Ok! 1581 queries used. |
| 3 |
Correct |
160 ms |
1076 KB |
Ok! 1540 queries used. |
| 4 |
Correct |
153 ms |
948 KB |
Ok! 1434 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
151 ms |
960 KB |
Ok! 1409 queries used. |
| 2 |
Correct |
152 ms |
952 KB |
Ok! 1404 queries used. |
| 3 |
Correct |
180 ms |
960 KB |
Ok! 1564 queries used. |
| 4 |
Correct |
146 ms |
852 KB |
Ok! 1423 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
175 ms |
956 KB |
Ok! 1550 queries used. |
| 2 |
Correct |
185 ms |
852 KB |
Ok! 1548 queries used. |
| 3 |
Correct |
171 ms |
960 KB |
Ok! 1546 queries used. |
| 4 |
Correct |
166 ms |
960 KB |
Ok! 1501 queries used. |
| 5 |
Correct |
165 ms |
1068 KB |
Ok! 1400 queries used. |
| 6 |
Correct |
151 ms |
960 KB |
Ok! 1434 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
173 ms |
852 KB |
Ok! 1542 queries used. |
| 2 |
Correct |
182 ms |
960 KB |
Ok! 1605 queries used. |
