oj.uz

Submission #789181

# Submission time Handle Problem Language Result Execution time Memory
789181 2023-07-21T07:07:37 Z enerelt14 The Big Prize (IOI17_prize) C++14
20 / 100
 75 ms 344 KB 
#include "prize.h"
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;
#define pb push_back

const int B = 472;
int val;

vector<int> find(int l, int r){
	vector<int> ans;
	if (l > r)return {};
	vector<int> x = ask(r);
	if (x[0] + x[1] != val){
		ans = find(l, r - 1);
		ans.pb(r);
		return ans;
	}
	int tl = l, tr = r;
	while (tl != tr){
		int mid = (tl + tr) / 2;
		vector<int> y = ask(mid);
		if (y[0] + y[1] != val){
			tl = mid + 1;
			continue;
		}
		if (y[1] != x[1])tl = mid + 1;
		else tr = mid;
	}
	if (l == tr)return {};
	else{
		ans = find(l, tr - 2);
		ans.pb(tr - 1);
		return ans;
	}
}

int find_best(int n){
	vector<int> non_lolipop, x;
	for (int i = 0; i < B; i++){
		x = ask(i);
		val = max(val, x[0] + x[1]);
	}
	for (int i = 0; i < n; i += B){
		x = find(i, min(n - 1, i + B - 1));
		for (int i = 0; i < x.size(); i++)non_lolipop.pb(x[i]);
	}
	for (int i = 0; i < non_lolipop.size(); i++){
		x = ask(non_lolipop[i]);
		if (x[0] + x[1] == 0)return non_lolipop[i];
	}
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for (int i = 0; i < x.size(); i++)non_lolipop.pb(x[i]);
      |                   ~~^~~~~~~~~~
prize.cpp:64:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for (int i = 0; i < non_lolipop.size(); i++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~
prize.cpp:55:14: warning: control reaches end of non-void function [-Wreturn-type]
   55 |  vector<int> non_lolipop, x;
      |              ^~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 208 KB Output is correct
2 Correct 16 ms 288 KB Output is correct
3 Correct 28 ms 208 KB Output is correct
4 Correct 39 ms 208 KB Output is correct
5 Correct 29 ms 208 KB Output is correct
6 Correct 34 ms 288 KB Output is correct
7 Correct 44 ms 208 KB Output is correct
8 Correct 38 ms 208 KB Output is correct
9 Correct 16 ms 328 KB Output is correct
10 Correct 32 ms 208 KB Output is correct

Subtask #2
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 208 KB Output is correct
2 Correct 21 ms 208 KB Output is correct
3 Correct 26 ms 296 KB Output is correct
4 Correct 33 ms 292 KB Output is correct
5 Correct 16 ms 292 KB Output is correct
6 Correct 16 ms 288 KB Output is correct
7 Correct 16 ms 284 KB Output is correct
8 Correct 37 ms 208 KB Output is correct
9 Correct 32 ms 208 KB Output is correct
10 Correct 40 ms 208 KB Output is correct
11 Partially correct 29 ms 208 KB Partially correct - number of queries: 5024
12 Partially correct 44 ms 208 KB Partially correct - number of queries: 5009
13 Partially correct 24 ms 288 KB Partially correct - number of queries: 5043
14 Correct 18 ms 208 KB Output is correct
15 Partially correct 73 ms 208 KB Partially correct - number of queries: 8718
16 Partially correct 54 ms 208 KB Partially correct - number of queries: 9255
17 Partially correct 74 ms 208 KB Partially correct - number of queries: 8842
18 Partially correct 75 ms 288 KB Partially correct - number of queries: 9317
19 Partially correct 29 ms 292 KB Partially correct - number of queries: 8624
20 Partially correct 45 ms 280 KB Partially correct - number of queries: 5542
21 Partially correct 72 ms 208 KB Partially correct - number of queries: 9041
22 Partially correct 62 ms 344 KB Partially correct - number of queries: 7784
23 Correct 47 ms 292 KB Output is correct
24 Partially correct 32 ms 208 KB Partially correct - number of queries: 5002
25 Partially correct 57 ms 292 KB Partially correct - number of queries: 8996
26 Partially correct 45 ms 208 KB Partially correct - number of queries: 8980
27 Correct 26 ms 256 KB Output is correct
28 Partially correct 61 ms 280 KB Partially correct - number of queries: 9197
29 Partially correct 67 ms 292 KB Partially correct - number of queries: 8352
30 Partially correct 51 ms 276 KB Partially correct - number of queries: 9296
31 Partially correct 65 ms 208 KB Partially correct - number of queries: 8838
32 Partially correct 32 ms 208 KB Partially correct - number of queries: 5029
33 Incorrect 1 ms 300 KB Integer 100 violates the range [0, 99]
34 Halted 0 ms 0 KB -