oj.uz

답안 #781993

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
781993 2023-07-13T14:36:33 Z TheSahib 커다란 상품 (IOI17_prize) C++14
20 / 100
 1000 ms 15604 KB 
#include "prize.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX = 2e5 + 5;
const int BLOCK = 500;

int tree[MAX];

void update(int pos, int val){
    while(pos < MAX){
        tree[pos] += val;
        pos += pos & (-pos);
    }
}

int ask(int l, int r){
    if(r < l) return 0;
    if(l != 1) return ask(1, r) - ask(1, l - 1);
    int ans = 0;
    while(r > 0){
        ans += tree[r];
        r -= r & (-r);
    }
    return ans;
}

int intRand(){
    return (rand() << 14) | rand();
}

vector<int> mp[MAX];

vector<int> query(int i){
    if(!mp[i].empty()) return mp[i];
    return mp[i] = ask(i - 1);
}


int find_best(int n) {
    vector<int> order(n);
    srand(time(0));
    iota(order.begin(), order.end(), 1);
    random_shuffle(order.begin(), order.end());
    vector<int> a;
    int cnt = 0;
    
    set<int> st;
    for (int i = 0; i < n; i++)
    {
        st.insert(i + 1);
    }
    for (int j = 0; j < min(450, (int)order.size()); ++j)
    {
        int i = order[j];
        a = query(i);
        if(a[0] + a[1] == 0) return i - 1;
        if(a[0] + a[1] < cnt){
            update(i, 1);
            st.erase(i);

        }
        else{
            cnt = a[0] + a[1];
        }
    }
    
    vector<int> blocks;
    int c = 0;
    while(true){
        auto itr = st.lower_bound(c);
        if(itr == st.end()) break;
        a = query(*itr);
        if(a[0] + a[1] == 0) return (*itr) - 1;
        if(a[0] + a[1] < cnt){
            update(*itr, 1);
            st.erase(itr);
            continue;
        }
        c = *itr;
        blocks.push_back(c);
        c += BLOCK;
    }
    if(*prev(st.end()) != blocks.back()){
        blocks.push_back(*prev(st.end()));
    }
    
    
    for (int i = 0; i < blocks.size() - 1; i++)
    {
        int b1 = blocks[i], b2 = blocks[i + 1];
        while(query(b1)[2] - query(b2)[2] - ask(b1, b2) != 0);
        {
            int l = b1, r = b2;
            while(l <= r){
                int x = (l + r) / 2;
                auto itr = st.lower_bound(x);
                if(itr == st.end() || (*itr) > r){
                    --itr;
                }
                int mid = *itr;
    
                a = query(mid);
    
                if(a[0] + a[1] == 0){
                    return mid - 1;
                }
                if(a[0] + a[1] < cnt && !ask(mid, mid)){
                    update(mid, 1);
                    st.erase(mid);
                    break;
                }
                a[0] -= query(b1)[0] + ask(b1, mid - 1);
                a[1] -= query(b2)[1] + ask(mid + 1, b2);
    
    
                if(a[1] > 0){
                    l = mid + 1;
                }
                else{
                    r = mid - 1;
                }
            }
        }
    }
    
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:90:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for (int i = 0; i < blocks.size() - 1; i++)
      |                     ~~^~~~~~~~~~~~~~~~~~~
prize.cpp:93:9: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
   93 |         while(query(b1)[2] - query(b2)[2] - ask(b1, b2) != 0);
      |         ^~~~~
prize.cpp:94:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
   94 |         {
      |         ^
prize.cpp:42:24: warning: control reaches end of non-void function [-Wreturn-type]
   42 |     vector<int> order(n);
      |                        ^

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 15096 KB Output is correct
2 Correct 57 ms 15216 KB Output is correct
3 Correct 56 ms 15176 KB Output is correct
4 Correct 53 ms 15292 KB Output is correct
5 Correct 41 ms 15124 KB Output is correct
6 Correct 40 ms 15096 KB Output is correct
7 Correct 51 ms 15080 KB Output is correct
8 Correct 43 ms 15100 KB Output is correct
9 Correct 77 ms 15224 KB Output is correct
10 Correct 68 ms 15176 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 67 ms 15196 KB Output is correct
2 Correct 74 ms 15216 KB Output is correct
3 Correct 51 ms 15440 KB Output is correct
4 Correct 79 ms 15240 KB Output is correct
5 Correct 57 ms 15188 KB Output is correct
6 Correct 104 ms 15152 KB Output is correct
7 Correct 117 ms 15120 KB Output is correct
8 Correct 46 ms 15104 KB Output is correct
9 Correct 84 ms 15184 KB Output is correct
10 Correct 73 ms 15220 KB Output is correct
11 Correct 54 ms 15372 KB Output is correct
12 Correct 42 ms 15192 KB Output is correct
13 Correct 76 ms 15604 KB Output is correct
14 Execution timed out 3046 ms 6096 KB Time limit exceeded
15 Halted 0 ms 0 KB -