oj.uz

Submission #699682

# Submission time Handle Problem Language Result Execution time Memory
699682 2023-02-17T17:51:25 Z urosk Park (JOI17_park) C++14
67 / 100
 405 ms 588 KB 
#include "park.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
#define maxn 1405
static int pl[1400];
ll n;
bool ok[maxn],use[maxn],lif[maxn];
ll deg[maxn],dpt[maxn];
bool ask(ll x,ll y){
    if(x>y) swap(x,y);
    for(ll i = 0;i<n;i++) pl[i] = use[i];
    pl[x] = pl[y] = 1;
    //cerr<<"ask: "<<x<< " "<<y<<endl;
    //ceri(pl,0,n-1);
    return Ask(x,y,pl);
}
void add(ll x,ll y){
    if(x>y) swap(x,y);
    //cerr<<"uv: "<<x<< " "<<y<<endl;
    Answer(x,y);
}
ll get(ll x){
    ll l = 0,r = n-1,mid,rez;
    while(l<=r){
        mid = (l+r)/2;
        for(ll i = 0;i<n;i++) use[i] = ok[i];
        for(ll i = 0;i<=mid;i++) use[i] = 1;
        if(!ask(0,x)){
            rez = mid;
            l = mid+1;
        }else r = mid-1;
    }
    rez++;
    //cerr<<"get: "<<x<< " "<<rez<<endl;
    return rez;
}
bool cmp(ll x,ll y){
    return dpt[x]<dpt[y];
}
vector<ll> v;
void reshi(ll x){
    //here;
    //ceri(ok,0,n-1);
    //dbg(x);
    for(ll i = 0;i<n;i++) use[i] = ok[i];
    while(!ask(0,x)){
        reshi(get(x));
        for(ll i = 0;i<n;i++) use[i] = ok[i];
    }
    ll l = 0,r = sz(v)-1,mid,rez;
    //cer(v);
    while(l<=r){
        mid = (l+r)/2;
        for(ll i = 0;i<=n;i++) use[i] = 0;
        for(ll i = 0;i<=mid;i++) use[v[i]] = 1;
        if(ask(x,0)){
            rez = mid;
            r = mid-1;
        }else l = mid+1;
    }
    rez = v[rez];
    ok[x] = 1;
    dpt[x] = dpt[rez]+1;
    add(x,rez);
    v.pb(x);
    sort(all(v),cmp);
}
void Detect(int T,int N){
    n = N;
    ok[0] = 1;
    v.pb(0);
    lif[0] = 1;
    for(ll i = 1;i<n;i++) if(!ok[i]) reshi(i);
    return;
}
/*
1
6
7
0 1
0 3
1 2
1 4
2 4
2 5
3 4

1
6
5
0 1
1 2
1 4
2 5
3 4
*/

Compilation message

park.cpp: In function 'long long int get(long long int)':
park.cpp:54:8: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |     rez++;
      |     ~~~^~
park.cpp: In function 'void reshi(long long int)':
park.cpp:82:16: warning: 'rez' may be used uninitialized in this function [-Wmaybe-uninitialized]
   82 |     rez = v[rez];
      |                ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 392 ms 488 KB Output is correct
2 Correct 126 ms 552 KB Output is correct
3 Correct 168 ms 468 KB Output is correct
4 Correct 405 ms 468 KB Output is correct
5 Correct 401 ms 472 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 412 KB Output is correct
2 Correct 202 ms 428 KB Output is correct
3 Correct 211 ms 400 KB Output is correct
4 Correct 171 ms 404 KB Output is correct
5 Correct 233 ms 420 KB Output is correct
6 Correct 207 ms 556 KB Output is correct
7 Correct 189 ms 424 KB Output is correct
8 Correct 204 ms 436 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 107 ms 388 KB Output is correct
2 Correct 253 ms 444 KB Output is correct
3 Correct 250 ms 340 KB Output is correct
4 Correct 282 ms 564 KB Output is correct
5 Correct 261 ms 448 KB Output is correct
6 Correct 280 ms 468 KB Output is correct
7 Correct 295 ms 460 KB Output is correct
8 Correct 245 ms 460 KB Output is correct
9 Correct 255 ms 560 KB Output is correct
10 Correct 280 ms 444 KB Output is correct
11 Correct 267 ms 448 KB Output is correct
12 Correct 233 ms 572 KB Output is correct
13 Correct 309 ms 460 KB Output is correct
14 Correct 254 ms 440 KB Output is correct
15 Correct 306 ms 436 KB Output is correct
16 Correct 209 ms 432 KB Output is correct
17 Correct 394 ms 588 KB Output is correct
18 Correct 268 ms 576 KB Output is correct
19 Correct 318 ms 468 KB Output is correct
20 Correct 249 ms 544 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 532 KB Wrong Answer[6]
2 Halted 0 ms 0 KB -