제출 #1155361

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1155361		onbert	커다란 상품 (IOI17_prize)	C++17	20 / 100	23 ms	5376 KiB

prize

#include <bits/stdc++.h>
using namespace std;

vector<int> ask(int i);

const int maxn = 2e5 + 5;
vector<int> ans[maxn];
vector<int> qry(int i) {
    if (ans[i].size() == 2) return ans[i];
    else {
        return ans[i] = ask(i);
    }
}

int find_best(int n) {
    int mx = 0;
    for (int i=0;i<500;i++) {
        int val = qry(i)[0] + qry(i)[1];
        if (val == 0) return i;
        mx = max(val, mx);
    }
    int cnt = 0, ans;
	for (int i=500;i<n;i++) {
        vector<int> vec = qry(i);
        if (vec[0] + vec[1] == 0) ans = i;
        if (vec[0] + vec[1] == mx) {
            if (qry(i+1) == vec) {
                if (i+2 < n && qry(i+2) == vec) {
                    cnt++;
                    int l = i+2, r = n-1;
                    while (l < r) {
                        int mid = (l+r+1)/2;
                        if (qry(mid) == vec) l = mid;   
                        else r = mid-1;
                    }
                    i = l;
                } else i++;
            }
        }
    }
    assert(cnt <= 170);
	return ans;
}

• Subtask 1: 20 / 20
• Subtask 2: 0 / 80