oj.uz

답안 #789262

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
789262 2023-07-21T08:43:32 Z enerelt14 커다란 상품 (IOI17_prize) C++14
0 / 100
 13 ms 11216 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

int val, B, y;
vector<int> non_lolipop, x, L;

vector<vector<int>> memo;
vector<int> K(int i) {
	if(i >= (int)memo.size()) exit(0);
	if(memo[i][0] != -1) return memo[i];
	return ask(i);
}

void find(int l, int r){
	if (l > r || K(l)[1] == y)return;
	if(K(l)[0] + K(l)[1] != val) {
		non_lolipop.pb(l);
		find(l + 1, r);
		return;
	}
	int bl = l, br = r;
	while (bl != br){
		int bm = (bl + br) / 2;
		if (K(bm) == K(l)) {
			bl = bm + 1;
		} else {
			br = bm;
		}
	}
	find(bl, r);
}

int find_best(int n){
	memo.resize(n, {-1, -1});
	B = max(1, n / 472);
	for (int i = 0; i < n; i += B){
		x = K(i);
		val = max(val, x[0] + x[1]);
	}
	// for (int i = 0; i < n; i += B){
	// 	for (int j = i; j < i + B && j < n; j++){
	// 		x = K(j);
	// 		if (x[0] + x[1] != val){
	// 			non_lolipop.pb(j);
	// 			continue;
	// 		}
	// 		L.pb(j);
	// 		break;
	// 	}
	// }
	// for (int i = 0; i < (int)L.size(); i++){
	// 	if (i + 1 == (int)L.size()){
	// 		x = K(L[i]);
	// 		y = max(0, n - (L[i] / B + 1) * B);
	// 	}else{
	// 		y = B * (L[i + 1] / B - L[i] / B - 1) + L[i + 1] % B;
	// 		x = K(L[i]);
	// 		vector<int> z = K(L[i + 1]);
	// 		y += z[1];
	// 	}
	// 	//find(L[i], min(n - 1, L[i] / B * B + B - 1));
	// }
	// for (int i = 0; i < non_lolipop.size(); i++){
	// 	x = K(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:86:1: warning: no return statement in function returning non-void [-Wreturn-type]
   86 | }
      | ^

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 13 ms 11216 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 11 ms 11208 KB Unexpected end of file - token expected
2 Halted 0 ms 0 KB -