oj.uz

Submission #727645

# Submission time Handle Problem Language Result Execution time Memory
727645 2023-04-21T04:48:40 Z jwvg0425 The Big Prize (IOI17_prize) C++17
20 / 100
 86 ms 1112 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 = 3;

int cnt(int l, int r)
{
	return upper_bound(all(finded), ii{ r, 1 << 30 }) - lower_bound(all(finded), ii{ l, -1 });
}

void test(int n, int l, int r)
{
	if (l > r)
		return;

	int ml = (l + r) / 2;
	int mlc = 0, mrc = 0;
	int mr = (l + r) / 2 + 1;

	while (ml >= l)
	{
		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] });
			ml--;
		}
		else
		{
			mlc = res[0];
			break;
		}
	}

	while (mr <= r)
	{
		auto res = ask(mr);
		if (res[0] + res[1] != bigSize)
		{
			finded.insert(lower_bound(all(finded), ii{ mr, res[0] + res[1] }), ii{ mr, res[0] + res[1] });
			mr++;
		}
		else
		{
			mrc = res[1];
			break;
		}
	}

	if (ml > l && mlc != cnt(0, ml - 1))
		test(n, l, ml - 1);

	if (mr < r && mrc != cnt(mr + 1, n - 1))
		test(n, mr + 1, r);
}

random_device rd;

int find_best(int n)
{
	mt19937 mt(rd());
	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 6 ms 1040 KB Output is correct
2 Correct 6 ms 1064 KB Output is correct
3 Correct 7 ms 1064 KB Output is correct
4 Correct 7 ms 1044 KB Output is correct
5 Correct 6 ms 1060 KB Output is correct
6 Correct 6 ms 1048 KB Output is correct
7 Correct 6 ms 1112 KB Output is correct
8 Correct 6 ms 1052 KB Output is correct
9 Correct 7 ms 1056 KB Output is correct
10 Correct 7 ms 1108 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1040 KB Output is correct
2 Correct 5 ms 1048 KB Output is correct
3 Correct 7 ms 1044 KB Output is correct
4 Correct 6 ms 1064 KB Output is correct
5 Correct 6 ms 1060 KB Output is correct
6 Correct 6 ms 1080 KB Output is correct
7 Correct 6 ms 972 KB Output is correct
8 Correct 7 ms 976 KB Output is correct
9 Correct 6 ms 976 KB Output is correct
10 Correct 6 ms 976 KB Output is correct
11 Correct 35 ms 968 KB Output is correct
12 Correct 17 ms 1084 KB Output is correct
13 Correct 33 ms 1072 KB Output is correct
14 Correct 36 ms 368 KB Output is correct
15 Incorrect 86 ms 1084 KB Incorrect
16 Halted 0 ms 0 KB -