제출 #98912

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
98912		square1001	커다란 상품 (IOI17_prize)	C++14	20 / 100	249 ms	644 KiB

prize

#include "prize.h"
#include <map>
#include <random>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct infos {
	int pos, left, right;
	infos(int pos_, int left_, int right_) : pos(pos_), left(left_), right(right_) {};
};
mt19937 mt(1902272037);
int rand_rng(int l, int r) {
	uniform_int_distribution<int> p(l, r - 1);
	return p(mt);
}
vector<int> random_pos(int n, int m) {
	vector<int> ans;
	for(int i = 0; i < m; ++i) {
		int x = -1;
		while(x == -1 || find(ans.begin(), ans.end(), x) != ans.end()) {
			x = rand_rng(0, n);
		}
		ans.push_back(x);
	}
	sort(ans.begin(), ans.end());
	return ans;
}
int find_best(int n) {
	vector<int> samples = random_pos(n, min(n, 5));
	int all = 0;
	for(int i : samples) {
		vector<int> res = ask(i);
		all = max(all, res[0] + res[1]);
	}
	vector<infos> v = { infos(-1, 0, all), infos(n, all, 0) };
	vector<int> s;
	while(true) {
		int maxd = 0, ptr = -1, mrem = -1;
		for(int i = 0; i < int(v.size()) - 1; ++i) {
			int rem = v[i].right + v[i + 1].left - all;
			rem -= lower_bound(s.begin(), s.end(), v[i + 1].pos) - lower_bound(s.begin(), s.end(), v[i].pos);
			if(rem > 0 && v[i + 1].pos - v[i].pos > maxd) {
				maxd = v[i + 1].pos - v[i].pos;
				ptr = i;
				mrem = rem;
			}
		}
		if(ptr == -1) break;
		if(maxd >= 2) {
			int m = (v[ptr].pos + v[ptr + 1].pos) / 2;
			vector<int> res = ask(m);
			if(res[0] + res[1] == 0) return m;
			if(res[0] + res[1] == all) {
				v.insert(v.begin() + ptr + 1, infos(m, res[0], res[1]));
			}
			else {
				--mrem;
				s.push_back(m);
				int cm = m - 1, flag = 0;
				while(mrem > 0 && cm > v[ptr].pos) {
					vector<int> res2 = ask(cm);
					if(res2[0] + res2[1] == 0) return cm;
					if(res2[0] + res2[1] == all) {
						v.insert(v.begin() + ptr + 1, infos(cm, res2[0], res2[1]));
						flag = 1;
						break;
					}
					s.push_back(cm);
					--mrem;
					--cm;
				}
				cm = m + 1;
				while(mrem > 0 && cm < v[ptr + 1].pos) {
					vector<int> res2 = ask(cm);
					if(res2[0] + res2[1] == 0) return cm;
					if(res2[0] + res2[1] == all) {
						v.insert(v.begin() + ptr + 1 + flag, infos(cm, res2[0], res2[1]));
						break;
					}
					s.push_back(cm);
					--mrem;
					++cm;
				}
				sort(s.begin(), s.end());
			}
		}
	}
	return -1;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80