oj.uz

Submission #727698

# Submission time Handle Problem Language Result Execution time Memory
727698 2023-04-21T06:28:46 Z jwvg0425 The Big Prize (IOI17_prize) C++17
20 / 100
 25 ms 1120 KB 
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#include "prize.h"
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
 
using namespace std;
 
template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>; 
 
vector<ii> finded;
int bigSize;
 
random_device rd;
mt19937 mt(rd());
int outL, outR;
 
int cntl(int x)
{
	return upper_bound(all(finded), ii{ x, 1 << 30 }) - finded.begin() + outL;
}
 
int cntr(int x)
{
	return finded.end() - lower_bound(all(finded), ii{ x, -1 }) + outR;
}
 
bool test(int l, int r)
{
	if (l > r)
		return false;
 
	int m = (l + r) / 2;
	int ml = m;
	int mlL = 0, mlR = 0;
 
	while (ml >= l)
	{
		if (any_of(all(finded), [ml](ii x) { return x.xx == ml; }))
		{
			ml--;
			continue;
		}
 
		auto res = ask(ml);
		if (res[0] + res[1] != bigSize)
		{
			finded.insert(lower_bound(all(finded), ii{ ml, res[0] + res[1] }), ii{ ml, res[0] + res[1] });
			if (res[0] + res[1] == 0)
				return true;
			ml--;
		}
		else
		{
			mlL = res[0];
			mlR = res[1];
			break;
		}
	}
 
	if (ml > l && mlL != cntl(ml - 1))
		if (test(l, ml - 1))
			return true;
 
	if (m + 1 <= r && mlR - (m - ml) != cntr(m + 1))
		if (test(m + 1, r))
			return true;
 
	return false;
}
 
int find_best(int n)
{
	vector<int> indexs(n);
	for (int i = 0; i < n; i++)
		indexs[i] = i;
 
	shuffle(all(indexs), mt);
	vector<ii> ix;
	for (int i = 0; i < min(n, 1000); i++)
	{
		auto q = ask(indexs[i]);
		if (q[0] + q[1] == 0)
			return i;
      
		ix.emplace_back(q[0] + q[1], indexs[i]);
	}
 
	sort(all(ix));
 
	bigSize = ix.back().xx;
	int bucket = 500;
	vector<int> bs;
 
	for (int i = 0; i < n; i += bucket)
		bs.push_back(i);
 
	shuffle(all(bs), mt);
 
	for (auto& bi : bs)
	{
		finded.clear();
		int l = bi, r = min(n - 1, bi + bucket - 1);
 
		while (l < r)
		{
			auto q = ask(l);
			if (q[0] + q[1] == 0)
				return l;
 
			if (q[0] + q[1] == bigSize)
			{
				outL = q[0];
				break;
			}
 
			l++;
		}
 
		while (l < r)
		{
			auto q = ask(r);
			if (q[0] + q[1] == 0)
				return r;
 
			if (q[0] + q[1] == bigSize)
			{
				outR = q[1];
				break;
			}
 
			r--;
		}
 
		// 한 개도 없는 구간 pass
		if (outL + outR == bigSize)
			continue;
 
		if (test(l + 1, r - 1))
		{
			for (auto& [k, v] : finded)
			{
				if (v == 0)
					return k;
			}
		}
	}
 
	return 0;
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1120 KB Output is correct
2 Correct 11 ms 1072 KB Output is correct
3 Correct 19 ms 1068 KB Output is correct
4 Correct 17 ms 1096 KB Output is correct
5 Correct 15 ms 1068 KB Output is correct
6 Correct 16 ms 1096 KB Output is correct
7 Correct 17 ms 1104 KB Output is correct
8 Correct 20 ms 984 KB Output is correct
9 Correct 10 ms 1112 KB Output is correct
10 Correct 25 ms 1116 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1072 KB Output is correct
2 Correct 18 ms 1068 KB Output is correct
3 Correct 17 ms 1104 KB Output is correct
4 Incorrect 7 ms 1068 KB answer is not correct
5 Halted 0 ms 0 KB -