oj.uz

Submission #731849

# Submission time Handle Problem Language Result Execution time Memory
731849 2023-04-28T05:33:44 Z sentheta The Big Prize (IOI17_prize) C++17
20 / 100
 55 ms 5084 KB 
#include "prize.h"
// author : sentheta aka vanwij
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cassert>
#include<random>
#include<chrono>
#include<cmath>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;

#define Int long long
#define V vector
#define pii pair<int,int>
#define ff first
#define ss second

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pow2(x) (1LL<<(x))
#define msb(x) (63-__builtin_clzll(x))
#define bitcnt(x) (__builtin_popcountll(x))

#define nl '\n'
#define _ << ' ' <<
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define dbg(x) if(1) cout << "?" << #x << " : " << (x) << endl << flush;


const int N = 2e5+5;
V<int> memo[N];
pii query(int i){
	if(memo[i].empty()) memo[i] = ask(i);
	return {memo[i][0], memo[i][1]};
}

int n;

#define mid (tl+tr)/2
#define lc (v+1)
#define rc (v+2*(mid-tl+1))
struct Segtree{
	int cnt[2*N];
	void upd(int i,int v=0,int tl=0,int tr=n-1){
		if(tl==tr){
			cnt[i] = 1; return;
		}
		if(i<=mid) upd(i, lc,tl,mid);
		else upd(i, rc,mid+1,tr);
		cnt[v] = cnt[lc] + cnt[rc];
	}
	int qry(int l,int r,int v=0,int tl=0,int tr=n-1){
		if(r<tl || tr<l) return 0;
		if(l<=tl && tr<=r) return cnt[v];
		return qry(l,r, lc,tl,mid) + qry(l,r, rc,mid+1,tr);
	}
} segtree;
#undef mid



int mx = 0;
int dnc(int lout=0,int rout=0,int l=474,int r=n-1){
	if(l > r) return -1;
	if(lout+rout+segtree.qry(l,r) == mx) return -1;

	int midcnt = 0;
	for(int m=(l+r)/2; m<=r; m++){
		auto[lcnt,rcnt] = query(m);
		if(lcnt+rcnt==0) return m;
		if(lcnt+rcnt < mx){
			midcnt++; continue;
		}

		if(lcnt > lout+midcnt){
			int i = dnc(lout,midcnt+rcnt, l,(l+r)/2-1);
			if(i!=-1) return i;
		}
		if(rcnt > rout){
			int i = dnc(lcnt,rout, m+1,r);
			if(i!=-1) return i;
		}
		return -1;
	}

	for(int m=(l+r)/2-1; m>=l; m--){
		auto[lcnt,rcnt] = query(m);
		if(lcnt+rcnt==0) return m;
		if(lcnt+rcnt < mx){
			midcnt++; continue;
		}
		// assert(rcnt == midcnt + rout);

		if(lcnt > lout){
			int i = dnc(lout,rcnt, l,m-1);
			if(i!=-1) return i;
		}
		return -1;
	}

	return -1;
}

V<int> ord;
map<int,V<int>> mp;

int find_best(int _n){
	n = _n;


	// queue<pii> que;
	// que.push({0,n-1});
	// while(ord.size() < min(n,474)){
	// 	auto[l,r] = que.front(); que.pop();
	// 	if(l > r) continue;

	// 	int ml = -1, mr = -1;
	// 	for(int m=(l+r)/2-3; m<=(l+r)/2+3; m++) if(0<=m && m<n){
	// 		ord.push_back(m);

	// 		if(ml==-1) ml = m;
	// 		mr = m;
	// 	}
	// 	if(l<ml) que.push({l,ml-1});
	// 	if(mr<r) que.push({mr+1,r});
	// }
	// for(int i=0; i<min(n,242); i++) ord.push_back(i);
	// for(int i=n-1; i>=max(n-242,0); i--) ord.push_back(i);
	// rep(i,0,ord.size()){
	// 	swap(ord[i], ord[rng()%(i+1)]);
	// }

	// for(int i : ord){
	// for(int i=max(0,n/2-240); i<=min(n-1,n/2+240); i++){
	rep(i,0,474){
		auto[lcnt,rcnt] = query(i);
		if(lcnt+rcnt==0) return i;

		mp[lcnt+rcnt].push_back(i);
		mx = max(mx, lcnt+rcnt);

		if(mp.size()==4) break;
		if(lcnt+rcnt>277) break;
	}
	assert((int)mp.size()<=5);

	for(auto&[x,v] : mp){
		if(x==mx){

		}
		else{
			for(int i : v){
				segtree.upd(i);
			}
		}
	}

	int ans = dnc();
	return ans;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4944 KB Output is correct
2 Correct 9 ms 5000 KB Output is correct
3 Correct 6 ms 4944 KB Output is correct
4 Correct 7 ms 4984 KB Output is correct
5 Correct 5 ms 5084 KB Output is correct
6 Correct 3 ms 4996 KB Output is correct
7 Correct 5 ms 4992 KB Output is correct
8 Correct 7 ms 4996 KB Output is correct
9 Correct 6 ms 4944 KB Output is correct
10 Correct 7 ms 4944 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4992 KB Output is correct
2 Correct 9 ms 4988 KB Output is correct
3 Correct 9 ms 4996 KB Output is correct
4 Correct 9 ms 4996 KB Output is correct
5 Correct 8 ms 4992 KB Output is correct
6 Correct 4 ms 4996 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 10 ms 4944 KB Output is correct
9 Correct 5 ms 5016 KB Output is correct
10 Correct 7 ms 5000 KB Output is correct
11 Correct 9 ms 4944 KB Output is correct
12 Correct 8 ms 4980 KB Output is correct
13 Correct 12 ms 5004 KB Output is correct
14 Correct 10 ms 4944 KB Output is correct
15 Correct 12 ms 4944 KB Output is correct
16 Correct 40 ms 5020 KB Output is correct
17 Incorrect 55 ms 5068 KB Integer -1 violates the range [0, 199999]
18 Halted 0 ms 0 KB -