Submission #1202626

#	Time	Username	Problem	Language	Result	Execution time	Memory
1202626		ansori	Counting Mushrooms (IOI20_mushrooms)	C++20	80.71 / 100	7 ms	776 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int inf = 1e9;
const int N = 2e4 + 5;
int use_machine(std::vector<int> x);
mt19937_64 rng(696969);
int s , tim;
int rand(int n){
	ll x = rng();
	return abs(x) % (n + 1);
}
vector<int> t(N * 4);
void build(int v , int l , int r){
	if(r - l == 1) t[v] = 1;
	else {
		int m = (l + r) / 2;
		build(v * 2 , l , m);
		build(v * 2 + 1 , m , r);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
}
void update(int v , int l , int r , int j){
	if(r - l == 1) t[v] = 0;
	else{
		int m = (l + r) / 2;
		if(j < m) update(v * 2 , l , m , j);
		else update(v * 2 + 1 , m , r , j);
		t[v] = t[v * 2] + t[v * 2 + 1];
	}
}
int gett_ps(int v , int l , int r , int x){
	if(r - l == 1) return l;
	int m = (l + r) / 2;
	if(t[v * 2] >= x){
		return gett_ps(v * 2 , l , m , x);
	}
	else{
		return gett_ps(v * 2 + 1 , m , r , x - t[v * 2]);
	}
	return 0;
}
int get(int x){ return gett_ps(1 , 0 , s , x); }
void upd(int p){
	update(1 , 0 , s , p);
}
int count_mushrooms(int n) {
	s = n;
	build(1 , 0 , n);
	upd(0);
	int sz = n - 1;
	int ans = 1;
	vector<int> psa , psb;
	psa.push_back(0);
	int j = 1;
	while(j < n){
		vector<int> ps;
		bool pa = true;
		int msz = 0;
		if(psa.size() >= psb.size()){
			msz = psa.size();
			for(auto to : psa) ps.push_back(to);
		}
		else{
			pa = false;
			msz = psb.size();
			for(auto to : psb) ps.push_back(to);
		}
		int lps = j , c = 0;
		vector<int> qu;
		for(int i = j;i < min(n , j + msz); ++ i){
			// random
			int p0 = rand((-- sz));
			int rps = get(p0 + 1);
			lps = rps;
			upd(rps);
			qu.push_back(ps[i - j]);
			qu.push_back(rps);
			c ++;
		}
		j = min(n , j + msz);
		//cout << c << ' ' << pa << '\n';
		int k = use_machine(qu);
		if(! pa){
			ans += (k + 1) / 2;
			if(k % 2 == 0) psb.push_back(lps);
			else psa.push_back(lps);
		}
		else{
			ans += (c - (k + 1) / 2);
			if(k % 2 == 1) psb.push_back(lps);
			else psa.push_back(lps);			
		}
	}
	return ans;
}

• Subtask 1: 80.7143 / 100