oj.uz

답안 #760524

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
760524 2023-06-17T17:25:56 Z raysh07 커다란 상품 (IOI17_prize) C++17
0 / 100
 67 ms 1488 KB 
#include "prize.h"
#include <bits/stdc++.h> 
using namespace std;

const int N = 2e5 + 69;
vector <int> a;
int f[N], mx;
int n;

void upd(int x){
    x++;
    for (int i = x; i <= n; i += i & (-i)) f[i]++;
}

int query(int x){
    x++;
    int res = 0;
    for (int i = x; i; i -= i & (-i)) res += f[i];
    return res;
}

void report(int x){
    assert(false);
    upd(a[x]);
    a.erase(a.begin() + x);
}

int find(){
    int l = 0, r = a.size() - 1;
    
    while (l != r){
        int m = (l + r)/2;
        
        auto g = ask(a[m]);
        int g1 = query(a[m]);
        if (g[0] + g[1] < mx){
            if (g[0] + g[1] == 0) return a[m];
            report(m);
            return 0;
        }
        if (g1 < g[0]) {
            r = m - 1;
        } else {
            l = m + 1;
        }
    }
    
    auto g = ask(a[l]);
    if (g[0] + g[1] == 0) return a[l];
    report(l);
    return 0;
}

int find_best(int m) {
    n = m;
	for (int i = 0; i < min(n, 500); i++){
	    auto get = ask(i);
	    
	    mx = max(mx, get[0] + get[1]);
	}
	assert(mx == 1);
	
	for (int i = 0; i < n; i++) a.push_back(i);
	
	while (true){
	    int get = find();
	    if (get > 0) return get;
	}
	assert(false);
	return 0;
}

Subtask #1
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1344 KB Output is correct
2 Correct 6 ms 1452 KB Output is correct
3 Correct 3 ms 1452 KB Output is correct
4 Correct 3 ms 1464 KB Output is correct
5 Correct 3 ms 1488 KB Output is correct
6 Incorrect 34 ms 1452 KB Incorrect
7 Halted 0 ms 0 KB -

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1440 KB Output is correct
2 Correct 3 ms 1456 KB Output is correct
3 Correct 5 ms 1452 KB Output is correct
4 Correct 3 ms 1488 KB Output is correct
5 Correct 3 ms 1456 KB Output is correct
6 Incorrect 67 ms 1488 KB Incorrect
7 Halted 0 ms 0 KB -