| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 318354 |
2020-11-01T11:43:22 Z |
neki |
ICC (CEOI16_icc) |
C++14 |
|
144 ms |
740 KB |
#include <bits/stdc++.h>
#include "icc.h"
#define fore(i, a) for(auto&& i:a)
#define fi first
#define se second
#define ps(a) push_back(a)
#define pb(a) pop_back(a)
#define sc scanf
#define vc vector
#define pa pair<ll, ll>
#define ll int
#define loop(i, a, b) for(ll i=a;i<b;i++)
#define pool(i, a, b) for(ll i=a-1;i>=b;i--)
#define lb lower_bound
#define ub upper_bound
#define all(a) a.begin(), a.end()
#define llmax LLONG_MAX/2
#define llmin -LLONG_MAX/2
using namespace std;
#define mn 200100
#define pa pair<ll, ll>
#define ld long double
vc<vc<ll>> dsu;
ll que(ll sa, ll sb, vc<ll> a, vc<ll> b){
ll qa[sa], qb[sb];
loop(i, 0, sa) qa[i]=a[i];
loop(i, 0, sb) qb[i]=b[i];
return query(sa, sb, qa, qb);
}
void run(int n){
loop(i, 1, n+1) dsu.ps(vc<ll> {i});
loop(cnt, 0, n-1){
vc<pa> ints={make_pair(0, dsu.size())};
vc<ll> a[2];
do{
a[0].clear(), a[1].clear();
vc<pa> ne;
fore(v, ints){
if(v.se-v.fi>1)ne.ps(make_pair(v.fi, (v.fi+v.se)/2)), ne.ps(make_pair((v.fi+v.se)/2, v.se));
else ne.ps(v);
}
ints=ne;
bool br=0;
fore(v, ints){
loop(j, v.fi, v.se) a[br].insert(a[br].end(), all(dsu[j]));
br=!br;
}
}while(!que(a[0].size(), a[1].size(), a[0], a[1]));
while(a[0].size()>1){
vc<ll> b[2];
loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
if(que(a[1].size(), b[0].size(), a[1], b[0])) a[0]=b[0];
else a[0]=b[1];
}
swap(a[0], a[1]);
while(a[0].size()>1){
vc<ll> b[2];
loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
if(que(a[1].size(), b[0].size(), a[1], b[0])) a[0]=b[0];
else a[0]=b[1];
}
ll aa=a[0][0], ab=a[1][0];
ll da, db;
loop(j, 0, dsu.size()){
fore(v, dsu[j]) if(v==aa)da=j;
fore(v, dsu[j]) if(v==ab)db=j;
}
vc<ll> save=dsu[db];
dsu[da].insert(dsu[da].end(), all(save));
dsu.erase(dsu.begin()+db);
setRoad(aa, ab);
}
}
Compilation message
icc.cpp: In function 'void run(int)':
icc.cpp:13:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define loop(i, a, b) for(ll i=a;i<b;i++)
......
57 | loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
| ~~~~~~~~~~~~~~~~~
icc.cpp:57:13: note: in expansion of macro 'loop'
57 | loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
| ^~~~
icc.cpp:57:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
57 | loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
| ~^~~~~~~~~~~~~~
icc.cpp:13:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define loop(i, a, b) for(ll i=a;i<b;i++)
......
64 | loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
| ~~~~~~~~~~~~~~~~~
icc.cpp:64:13: note: in expansion of macro 'loop'
64 | loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
| ^~~~
icc.cpp:64:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | loop(j, 0, a[0].size()) b[j<a[0].size()/2].ps(a[0][j]);
| ~^~~~~~~~~~~~~~
icc.cpp:13:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | #define loop(i, a, b) for(ll i=a;i<b;i++)
......
72 | loop(j, 0, dsu.size()){
| ~~~~~~~~~~~~~~~~
icc.cpp:72:9: note: in expansion of macro 'loop'
72 | loop(j, 0, dsu.size()){
| ^~~~
icc.cpp:77:27: warning: 'db' may be used uninitialized in this function [-Wmaybe-uninitialized]
77 | vc<ll> save=dsu[db];
| ^
icc.cpp:78:15: warning: 'da' may be used uninitialized in this function [-Wmaybe-uninitialized]
78 | dsu[da].insert(dsu[da].end(), all(save));
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
492 KB |
Ok! 95 queries used. |
| 2 |
Correct |
6 ms |
492 KB |
Ok! 96 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
45 ms |
492 KB |
Ok! 548 queries used. |
| 2 |
Correct |
44 ms |
492 KB |
Ok! 654 queries used. |
| 3 |
Correct |
46 ms |
620 KB |
Ok! 627 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
492 KB |
Ok! 1455 queries used. |
| 2 |
Correct |
144 ms |
492 KB |
Ok! 1663 queries used. |
| 3 |
Correct |
132 ms |
492 KB |
Ok! 1575 queries used. |
| 4 |
Correct |
130 ms |
612 KB |
Ok! 1507 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
129 ms |
492 KB |
Ok! 1526 queries used. |
| 2 |
Correct |
138 ms |
492 KB |
Ok! 1540 queries used. |
| 3 |
Correct |
130 ms |
612 KB |
Ok! 1516 queries used. |
| 4 |
Correct |
130 ms |
524 KB |
Ok! 1515 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
133 ms |
584 KB |
Ok! 1543 queries used. |
| 2 |
Correct |
137 ms |
708 KB |
Ok! 1493 queries used. |
| 3 |
Correct |
134 ms |
608 KB |
Ok! 1548 queries used. |
| 4 |
Correct |
133 ms |
492 KB |
Ok! 1565 queries used. |
| 5 |
Correct |
127 ms |
620 KB |
Ok! 1490 queries used. |
| 6 |
Correct |
137 ms |
612 KB |
Ok! 1558 queries used. |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
141 ms |
612 KB |
Ok! 1515 queries used. |
| 2 |
Correct |
129 ms |
740 KB |
Ok! 1491 queries used. |
