제출 #760536

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

prize

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

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

vector <int> ask2(int x){
    if (mp.find(x) != mp.end()) return mp[x];
    return mp[x] = ask(x);
}

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){
    upd(a[x]);
    a.erase(a.begin() + x);
}

int find(){
    to.clear();
    
    set <pair<int, int>> s1;
    s1.insert({0, a.size() - 1});
    
    // while (l != r){
    //     // cout << l << " " << r << "\n";
    //     int m = (l + r)/2;
        
    //     auto g = ask2(a[m]);
    //     int g1 = query(a[m]);
        
    //     // cout << m << " " << g[0] << " " << g1 << "\n";
    //     if (g[0] + g[1] < mx){
    //         if (g[0] + g[1] == 0) return a[m];
    //         report(m);
    //         return -1;
    //     }
    //     if (g1 < g[0]) {
    //         r = m - 1;
    //     } else {
    //         l = m + 1;
    //     }
    // }
    
    while (true){
        bool good = true;
        set <pair<int, int>> s2;
        for (auto [x, y] : s1) {
            if (x != y) good = false;
        }
        
        if (good) break;
        
        for (auto [l, r] : s1){
            if (l == r) continue;
            int m = (l + r)/2;
            
            auto g = ask2(a[m]);
            int g1 = query(a[m]);
            int g2 = query(n - 1) - query(a[m]);
            
            if (g[0] + g[1] < mx){
                if (g[0] + g[1] == 0) return a[m];
                to.push_back(m);
            }
            if (g1 < g[0]) s2.insert({l, m - 1});
            if (g2 < g[1]) s2.insert({m + 1, r});
        }
        s1 = s2;
    }
    
    // cout << l << " " << r << "\n";
    for (auto [l, r] : s1){
        auto g = ask2(a[l]);
        if (g[0] + g[1] == 0) return a[l];
        to.push_back(l);
    }
    
    sort(to.begin(), to.end(), greater<int>());
    for (auto x : to) report(x);
    
    return -1;
}

int find_best(int m) {
    n = m;
    vector<vector<int>> ok;
	for (int i = 0; i < min(n, 500); i++){
	    auto get = ask2(i);
	    ok.push_back(get);
	    
	    mx = max(mx, get[0] + get[1]);
	}
	
// 	if (mx != 1){
// 	    cout << n << "\n";
// 	    for (auto x : ok){
// 	        for (auto y : x) cout << y << " ";
// 	        cout << "\n";
// 	    }
// 	    return 0;
// 	}
	
	for (int i = 0; i < n; i++) a.push_back(i);
	
	while (true){
	    int get = find();
	    if (get > -1) return get;
	}
	assert(false);
	return 0;
}

// int main(){
//     // int t; cin >> t;
    
//     // while (t--){
//     //     int n = 3 + rand() % 10;
//     //     int x = rand() % n;
        
//     //     a.clear();
//     //     mx = 0;
//     //     for (int i = 0; i <= n; i++) f[i] = 0, a1[i] = a2[i] = 0;
        
//     //     for (int i = 0; i < x; i++) a2[i] = 1;
//     //     for (int i = x + 1; i < n; i++) a1[i] = 1;
        
//     //     int get = find_best(n);
//     //     if (get != x){
//     //         cout << n << " " << x << "\n";
//     //         return 0;
//     //     }
//     // }
    
//     int n; cin >> n;
//     for (int i = 0; i < n; i++) cin >> a1[i];
//     for (int i = 0; i < n; i++) cin >> a2[i];
    
//     cout << find_best(n);
//     return 0;
// }

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