oj.uz

Submission #995009

# Submission time Handle Problem Language Result Execution time Memory
995009 2024-06-08T10:18:10 Z caterpillow The Big Prize (IOI17_prize) C++17
20 / 100
 65 ms 2404 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll, ll>;
using pi = pair<int, int>;
#define vt vector
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(), x.end() 
#define size(x) ((int) (x).size())
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--)
#define F0R(i, b) FOR (i, 0, b)
#define endl '\n'
const ll INF = 1e18;
const int inf = 1e9;

template<template<typename> class Container, typename T>
ostream& operator<<(ostream& os, Container<T> o) {
	os << "{"; 
	int g = size(o); 
	for (auto i : o) os << i << ((--g) == 0 ? "" : ", "); 
	os << "}";
	return os;
}

void _print() {
	cerr << "\n";
}

template<typename T, typename ...V>
void _print(T t, V... v) {
	cerr << t; if (sizeof...(v)) cerr << ", "; _print(v...);
}

#ifdef LOCAL
#define cerr(x...) cerr << #x << " = "; _print(x);
#else
#define cerr(x...)
#define cerr if (0) std::cerr
#endif

/*

there are at most O(sqrt n) different types of prizes
constraints suggest 2 * sqrt(n) * log2(n)
we can differentiate levels of boxes based on sum of query results
there are at most sqrt non-complete-trash prizes
if we can isolate each "level" of prizes, we can work our way up to the top

consider only the worst type of prize
there are at most sqrt(n) connected components of prizes better than this
we can bsearch for these components

to find a l point, move it right while the # of better prizes to its left doesnt change
to find a r point, move it right while the # of better prizes to its right doesnt change 
take these points, and squish the new array such that we only consider these indices now

do this recursively unitl we end up with an array of length 1

*/

map<int, pi> memo;
pi _query(int i) {
	if (memo.count(i)) return memo[i];
	vt<int> res = ask(i);
	return memo[i] = {res[0], res[1]};
}

struct Array {
	vt<int> actual;
	void pb(int v) {
		actual.pb(v);
	}
	pi query(int i) {
		if (i < 0) return {0, 0};
		return _query(actual[i]);
	}
	int operator[](int i) {
		return actual[i];
	}
	int sz() {
		return size(actual);
	}
};

/*

to find a l point, move it right while the # of better prizes to its left doesnt change (so query res is equal or less than original)
take these points, and squish the new array such that we only consider these indices now

*/

void solve(Array& a, int tot) {
	vt<pi> rngs; // inc, exc
	int n = a.sz();
	int l = -1, r;
	while (l < n) {
		int hi = n;
		int bruh = a.query(l).f;
		while (hi - l > 1) {
			int m = (l + hi) / 2;
			auto [x, y] = a.query(m);
			if (x + y == tot && x <= bruh) l = m;
			else hi = m;
		}
		l++;

		if (l == n) break; // reached end of arr
		int r = l + 1; // exc
		while (r < n) {
			auto [lhs, rhs] = a.query(r);
			if (lhs + rhs == tot) break;
			else r++;
		}
		rngs.pb({l, r});
		l = r;
	}
	Array narr;
	for (auto [l, r] : rngs) {
		FOR (i, l, r) {
			narr.pb(a[i]);
		}
	}
	a = narr;
}

int find_best(int _n) {
	Array arr;
	int n = _n;
	F0R (i, n) {
		arr.pb(i);
	}

	while (arr.sz() > 1) {
		int tot = 0;
		F0R (i, min(arr.sz(), (int) sqrt(arr.sz()) + 5)) {
			auto [l, r] = arr.query(i);
			tot = max(tot, l + r);
		}
		solve(arr, tot);
	}
	auto [l, r] = _query(arr[0]);
	assert(l + r == 0);
	return arr[0];
}

Compilation message

prize.cpp:44: warning: "cerr" redefined
   44 | #define cerr if (0) std::cerr
      | 
prize.cpp:43: note: this is the location of the previous definition
   43 | #define cerr(x...)
      | 
prize.cpp: In function 'void solve(Array&, int)':
prize.cpp:101:14: warning: unused variable 'r' [-Wunused-variable]
  101 |  int l = -1, r;
      |              ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1488 KB Output is correct
2 Correct 5 ms 1488 KB Output is correct
3 Correct 3 ms 1488 KB Output is correct
4 Correct 3 ms 1488 KB Output is correct
5 Correct 3 ms 1488 KB Output is correct
6 Correct 4 ms 1488 KB Output is correct
7 Correct 3 ms 1488 KB Output is correct
8 Correct 4 ms 1532 KB Output is correct
9 Correct 2 ms 1488 KB Output is correct
10 Correct 5 ms 1488 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1488 KB Output is correct
2 Correct 3 ms 1488 KB Output is correct
3 Correct 4 ms 1740 KB Output is correct
4 Correct 3 ms 1488 KB Output is correct
5 Correct 4 ms 1488 KB Output is correct
6 Correct 2 ms 1484 KB Output is correct
7 Correct 4 ms 1488 KB Output is correct
8 Correct 3 ms 1740 KB Output is correct
9 Correct 3 ms 1488 KB Output is correct
10 Correct 3 ms 1488 KB Output is correct
11 Correct 6 ms 1488 KB Output is correct
12 Correct 6 ms 1488 KB Output is correct
13 Correct 7 ms 1740 KB Output is correct
14 Correct 13 ms 656 KB Output is correct
15 Partially correct 36 ms 1488 KB Partially correct - number of queries: 7949
16 Partially correct 43 ms 1788 KB Partially correct - number of queries: 8367
17 Partially correct 38 ms 1732 KB Partially correct - number of queries: 8339
18 Partially correct 36 ms 1928 KB Partially correct - number of queries: 8340
19 Partially correct 63 ms 1840 KB Partially correct - number of queries: 7864
20 Partially correct 36 ms 1224 KB Partially correct - number of queries: 5441
21 Partially correct 54 ms 2404 KB Partially correct - number of queries: 8257
22 Partially correct 28 ms 1488 KB Partially correct - number of queries: 6259
23 Correct 4 ms 1488 KB Output is correct
24 Correct 7 ms 1488 KB Output is correct
25 Partially correct 46 ms 1620 KB Partially correct - number of queries: 8264
26 Partially correct 36 ms 1836 KB Partially correct - number of queries: 8187
27 Correct 4 ms 1488 KB Output is correct
28 Partially correct 56 ms 1584 KB Partially correct - number of queries: 8144
29 Partially correct 50 ms 1608 KB Partially correct - number of queries: 6730
30 Partially correct 59 ms 1944 KB Partially correct - number of queries: 8298
31 Partially correct 52 ms 1848 KB Partially correct - number of queries: 8312
32 Correct 8 ms 1488 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Partially correct 57 ms 2044 KB Partially correct - number of queries: 8334
35 Correct 5 ms 1488 KB Output is correct
36 Partially correct 42 ms 1536 KB Partially correct - number of queries: 8236
37 Correct 6 ms 1488 KB Output is correct
38 Correct 4 ms 1488 KB Output is correct
39 Partially correct 55 ms 1592 KB Partially correct - number of queries: 8281
40 Partially correct 42 ms 1732 KB Partially correct - number of queries: 7189
41 Partially correct 44 ms 1756 KB Partially correct - number of queries: 8205
42 Partially correct 49 ms 1780 KB Partially correct - number of queries: 8205
43 Partially correct 49 ms 1820 KB Partially correct - number of queries: 7810
44 Partially correct 43 ms 1704 KB Partially correct - number of queries: 8329
45 Partially correct 38 ms 1488 KB Partially correct - number of queries: 8263
46 Partially correct 57 ms 1860 KB Partially correct - number of queries: 8330
47 Partially correct 65 ms 1812 KB Partially correct - number of queries: 8334
48 Partially correct 53 ms 1592 KB Partially correct - number of queries: 8338
49 Partially correct 38 ms 1732 KB Partially correct - number of queries: 8300
50 Partially correct 58 ms 1616 KB Partially correct - number of queries: 8342
51 Partially correct 53 ms 1728 KB Partially correct - number of queries: 8300
52 Partially correct 38 ms 1732 KB Partially correct - number of queries: 8369
53 Correct 4 ms 1488 KB Output is correct
54 Partially correct 47 ms 2164 KB Partially correct - number of queries: 8276
55 Partially correct 46 ms 1848 KB Partially correct - number of queries: 8351
56 Partially correct 53 ms 1592 KB Partially correct - number of queries: 8342
57 Partially correct 43 ms 1728 KB Partially correct - number of queries: 8284
58 Partially correct 53 ms 1844 KB Partially correct - number of queries: 8312
59 Partially correct 59 ms 1732 KB Partially correct - number of queries: 8196
60 Partially correct 49 ms 1736 KB Partially correct - number of queries: 7845
61 Correct 4 ms 1500 KB Output is correct
62 Correct 4 ms 1488 KB Output is correct
63 Correct 5 ms 1488 KB Output is correct
64 Correct 4 ms 1488 KB Output is correct
65 Correct 3 ms 1488 KB Output is correct
66 Correct 5 ms 1488 KB Output is correct
67 Correct 6 ms 1488 KB Output is correct
68 Correct 4 ms 1488 KB Output is correct
69 Correct 5 ms 1488 KB Output is correct
70 Correct 5 ms 1488 KB Output is correct
71 Partially correct 59 ms 1588 KB Partially correct - number of queries: 8195
72 Correct 6 ms 1488 KB Output is correct
73 Partially correct 50 ms 1620 KB Partially correct - number of queries: 8102
74 Partially correct 43 ms 1920 KB Partially correct - number of queries: 8146
75 Correct 4 ms 1488 KB Output is correct
76 Partially correct 42 ms 1608 KB Partially correct - number of queries: 7070
77 Partially correct 46 ms 1960 KB Partially correct - number of queries: 8371
78 Correct 8 ms 1488 KB Output is correct
79 Correct 20 ms 1484 KB Output is correct
80 Partially correct 41 ms 1732 KB Partially correct - number of queries: 8360
81 Partially correct 41 ms 2008 KB Partially correct - number of queries: 8354
82 Partially correct 37 ms 1728 KB Partially correct - number of queries: 8322
83 Correct 4 ms 1488 KB Output is correct
84 Partially correct 34 ms 1732 KB Partially correct - number of queries: 6918
85 Partially correct 51 ms 1936 KB Partially correct - number of queries: 8350
86 Incorrect 55 ms 1796 KB Incorrect
87 Halted 0 ms 0 KB -