oj.uz

답안 #1080526

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1080526 2024-08-29T10:45:01 Z TB_ 커다란 상품 (IOI17_prize) C++17
20 / 100
 94 ms 37976 KB 
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fo(i, n) for(ll i = 0; i<(n); i++)
#define F first
#define S second
#define pb push_back
#define deb(x) cout << #x << " = " << (x) << endl
#define deb2(x, y) cout << #x << " = " << (x) << ", " << #y << " = " << (y) << endl

typedef vector<ll> vl;
typedef vector<vl> vvl;

int find_best(int n);
std::vector<int> ask(int i);
// std::vector<int> ask(int i){
//     // ll gaah = 2;
//     // if(i==gaah) return {0, 0};
//     // else if(i>gaah) return {1, 0};
//     // else return {0, 1};
//     if(i==0) return {0, 3};
//     if(i==1) return {0, 0};
//     if(i==2) return {1, 0};
//     if(i==3) return {2, 1};
//     if(i==4) return {2, 1};
//     if(i==5) return {1, 0};
//     else return {3, 0};
// }

ll valval = 1;

struct Node{
    Node *lnode, *rnode;
    ll l, r, val = valval;
    Node(ll l, ll r) : l(l), r(r){
        if(r-l>1){
            ll mid = (r+l) / 2;
            lnode = new Node(l, mid);
            rnode = new Node(mid, r);
            val = lnode->val+rnode->val;
        }
    }

    void update2(ll lo, ll hi){
        if(r <= lo || hi <= l) return;
        if(r <= hi && lo <= l){
            val = 1;
            return;
        }
        lnode->update2(lo, hi);rnode->update2(lo, hi); 
        val = lnode->val+rnode->val;
    }

    ll sumQuery(ll lo, ll hi){
        if(r <= lo || hi <= l) return 0;
        if(r <= hi && lo <= l) return val;
        return lnode->sumQuery(lo, hi)+rnode->sumQuery(lo, hi); 
    }

    ll query(ll x){
        if(r-l == 1){
            val = 0;
            return l;
        }
        ll res;
        if(lnode->val>x) res = lnode->query(x);
        else{
            x-=lnode->val;
            res = rnode->query(x);
        }
        val = lnode->val+rnode->val;
        return res;
    }
};

int find_best(int n){
    ll co = 0;
    ll prething = -1;
    mt19937 rng(42);
    fo(i, 500){
        ll temp = rng()%n;
        co++;
        vector<int> res = ask(temp);
        if(res[0] ==0 && res[1] == 0){
            return temp;
        }
        prething = max(prething, (ll)res[0]+res[1]);
    } 
    Node st(0, n);
    valval = 0;
    Node st2(0, n);
    while(1){
        // deb("gahh");
        ll lo = 0;
        ll hi = n;
        while(hi-lo>1){
            ll a = st.sumQuery(0, lo);
            ll b = st.sumQuery(0, hi);
            ll pos = st.query((a+b)/2);
            co++;
            vector<int> res = ask(pos);
            // deb(pos);
            if(res[0] ==0 && res[1] == 0){
                return pos;
            }
            if(res[0]+res[1] <prething){
                st2.update2(pos, pos+1);
                break;
            }
            res[0]-=st2.sumQuery(0, pos);
            if(res[0]) hi = pos;
            else lo = pos+1;
        }
    }
}

Compilation message

prize.cpp: In function 'int find_best(int)':
prize.cpp:68:12: warning: 'st.Node::lnode' may be used uninitialized in this function [-Wmaybe-uninitialized]
   68 |         if(lnode->val>x) res = lnode->query(x);
      |            ^~~~~
prize.cpp:71:19: warning: 'st.Node::rnode' may be used uninitialized in this function [-Wmaybe-uninitialized]
   71 |             res = rnode->query(x);
      |                   ^~~~~

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 29 ms 37968 KB Output is correct
2 Correct 30 ms 37968 KB Output is correct
3 Correct 28 ms 37856 KB Output is correct
4 Correct 27 ms 37972 KB Output is correct
5 Correct 29 ms 37808 KB Output is correct
6 Correct 29 ms 37968 KB Output is correct
7 Correct 28 ms 37968 KB Output is correct
8 Correct 33 ms 37968 KB Output is correct
9 Correct 26 ms 37968 KB Output is correct
10 Correct 26 ms 37976 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 37788 KB Output is correct
2 Correct 30 ms 37976 KB Output is correct
3 Correct 29 ms 37976 KB Output is correct
4 Correct 28 ms 37820 KB Output is correct
5 Correct 29 ms 37968 KB Output is correct
6 Correct 28 ms 37792 KB Output is correct
7 Correct 30 ms 37816 KB Output is correct
8 Correct 29 ms 37968 KB Output is correct
9 Correct 27 ms 37976 KB Output is correct
10 Correct 28 ms 37976 KB Output is correct
11 Correct 30 ms 37968 KB Output is correct
12 Correct 26 ms 37800 KB Output is correct
13 Correct 33 ms 37944 KB Output is correct
14 Correct 10 ms 4280 KB Output is correct
15 Correct 37 ms 37820 KB Output is correct
16 Partially correct 87 ms 37968 KB Partially correct - number of queries: 8979
17 Correct 26 ms 37964 KB Output is correct
18 Incorrect 94 ms 37976 KB Incorrect
19 Halted 0 ms 0 KB -