oj.uz

Submission #727660

# Submission time Handle Problem Language Result Execution time Memory
727660 2023-04-21T05:26:23 Z jwvg0425 The Big Prize (IOI17_prize) C++17
20 / 100
 109 ms 1104 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 cnt(int l, int r)
{
	return upper_bound(all(finded), ii{ r, 1 << 30 }) - lower_bound(all(finded), ii{ l, -1 });
}

bool test(int n, 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 != cnt(0, ml - 1))
		if (test(n, l, ml - 1))
			return true;

	if (m + 1 <= r && mlR - (m - ml) != cnt(m + 1, n - 1))
		if (test(n, 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, 30); i++)
	{
		auto q = ask(indexs[i]);
		ix.emplace_back(q[0] + q[1], indexs[i]);
	}

	sort(all(ix));

	bigSize = ix.back().xx;
	test(n, 0, n - 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 7 ms 1064 KB Output is correct
2 Correct 7 ms 1068 KB Output is correct
3 Correct 7 ms 1088 KB Output is correct
4 Correct 7 ms 1076 KB Output is correct
5 Correct 6 ms 1048 KB Output is correct
6 Correct 6 ms 1072 KB Output is correct
7 Correct 6 ms 1052 KB Output is correct
8 Correct 7 ms 1072 KB Output is correct
9 Correct 6 ms 1076 KB Output is correct
10 Correct 7 ms 1100 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1084 KB Output is correct
2 Correct 6 ms 1072 KB Output is correct
3 Correct 6 ms 1064 KB Output is correct
4 Correct 7 ms 1072 KB Output is correct
5 Correct 7 ms 1060 KB Output is correct
6 Correct 6 ms 1072 KB Output is correct
7 Correct 7 ms 1052 KB Output is correct
8 Correct 6 ms 1068 KB Output is correct
9 Correct 6 ms 1060 KB Output is correct
10 Correct 6 ms 1104 KB Output is correct
11 Correct 14 ms 1068 KB Output is correct
12 Correct 6 ms 976 KB Output is correct
13 Correct 25 ms 1064 KB Output is correct
14 Correct 5 ms 336 KB Output is correct
15 Correct 18 ms 1088 KB Output is correct
16 Incorrect 109 ms 1092 KB Incorrect
17 Halted 0 ms 0 KB -