This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "insects.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
vector<int> vc, vc2;
int cnt[N];
vector<iii> queries[13];
bool cmp(iii a, iii b){
return (a.fi.fi + a.fi.se < b.fi.fi + b.fi.se);
}
bool in[N];
void moveinside(int u){
if(in[u]) return;
move_inside(u);
in[u] = 1;
}
void moveoutside(int u){
if(!in[u]) return;
move_outside(u);
in[u] = 0;
}
int p[N];
int mx[N], pref[N];
int min_cardinality(int n){
for(int i = 0; i < n; i++) p[i] = i;
shuffle(p, p + n, default_random_engine(7405));
vc.pb(p[0]);
moveinside(p[0]);
for(int i = 1; i < n; i++){
moveinside(p[i]);
int temp = press_button();
if(temp >= 2){
moveoutside(p[i]);
mx[p[i]] = vc.size();
vc2.pb(p[i]);
}
else vc.pb(p[i]);
}
if(vc.size() >= 64){
for(int i = 0; i < vc.size(); i++) cnt[i] = 1;
for(int i = 0; i < vc2.size(); i++) queries[0].pb({{0, mx[vc2[i]] - 1}, vc2[i]});
//for(auto it : vc) moveoutside(it);
int lst = vc.size() - 1;
for(int i = 0; i <= 12; i++){
if(!queries[i].size()) break;
sort(queries[i].begin(), queries[i].end(), cmp);
for(auto it : queries[i]){
pref[it.fi.fi]++;
pref[it.fi.se + 1]--;
}
for(int i = 1; i < vc.size(); i++) pref[i] += pref[i - 1];
for(int i = 0; i < vc.size(); i++) if(pref[i] == 1) return 1;
if((i & 1)){
//cout << i << "\n";
//for(auto it : vc) assert(!in[it]);
for(auto it : queries[i]){
int mid = (it.fi.fi + it.fi.se) / 2;
if(it.fi.fi == it.fi.se){
cnt[it.fi.fi]++;
continue;
}
for(int temp = it.fi.fi; temp <= mid; temp++) moveinside(vc[temp]);
for(int temp = mid + 1; temp <= it.fi.se; temp++) moveoutside(vc[temp]);
/*
while(lst > mid){
moveoutside(vc[lst]);
lst--;
}
while(lst < mid){
lst++;
moveinside(vc[lst]);
}*/
moveinside(it.se);
if(press_button() >= 2) queries[i + 1].pb({{it.fi.fi, mid}, it.se});
else queries[i + 1].pb({{mid + 1, it.fi.se}, it.se});
moveoutside(it.se);
}
}
else{
//for(auto it : vc) if(!in[it]) cout << i << "\n";
reverse(queries[i].begin(), queries[i].end());
for(auto it : queries[i]){
int mid = (it.fi.fi + it.fi.se) / 2;
//assert(lst >= mid);
if(it.fi.fi == it.fi.se){
cnt[it.fi.fi]++;
continue;
}
for(int temp = it.fi.fi; temp <= mid; temp++) moveinside(vc[temp]);
for(int temp = mid + 1; temp <= it.fi.se; temp++) moveoutside(vc[temp]);
moveinside(it.se);
if(press_button() >= 2) queries[i + 1].pb({{it.fi.fi, mid}, it.se});
else queries[i + 1].pb({{mid + 1, it.fi.se}, it.se});
moveoutside(it.se);
}
}
}
int mn = oo;
for(int i = 0; i < vc.size(); i++) mn = min(mn, cnt[i]);
return mn;
}
else{
int l = 1, r = n / vc.size();
while(l < r){
int mid = (l + r + 1) >> 1;
for(int i = 0; i < n; i++) moveoutside(i);
for(int i = 0; i < n; i++){
moveinside(i);
if(press_button() > mid) moveoutside(i);
}
int total = 0;
for(int i = 0; i < n; i++) total += in[i];
if(total == mid * vc.size()) l = mid;
else r = mid - 1;
}
return l;
}
}
Compilation message (stderr)
insects.cpp:16:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
16 | const int oo = 1e18 + 7, mod = 1e9 + 7;
| ~~~~~^~~
insects.cpp: In function 'int min_cardinality(int)':
insects.cpp:62:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < vc.size(); i++) cnt[i] = 1;
| ~~^~~~~~~~~~~
insects.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int i = 0; i < vc2.size(); i++) queries[0].pb({{0, mx[vc2[i]] - 1}, vc2[i]});
| ~~^~~~~~~~~~~~
insects.cpp:73:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | for(int i = 1; i < vc.size(); i++) pref[i] += pref[i - 1];
| ~~^~~~~~~~~~~
insects.cpp:74:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
74 | for(int i = 0; i < vc.size(); i++) if(pref[i] == 1) return 1;
| ~~^~~~~~~~~~~
insects.cpp:121:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
121 | for(int i = 0; i < vc.size(); i++) mn = min(mn, cnt[i]);
| ~~^~~~~~~~~~~
insects.cpp:65:10: warning: unused variable 'lst' [-Wunused-variable]
65 | int lst = vc.size() - 1;
| ^~~
insects.cpp:135:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
135 | if(total == mid * vc.size()) l = mid;
| ~~~~~~^~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |