oj.uz

Submission #940998

# Submission time Handle Problem Language Result Execution time Memory
940998 2024-03-08T04:52:10 Z hotboy2703 Toxic Gene (NOI23_toxic) C++17
59.5 / 100
 12 ms 924 KB 
#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
#define MP make_pair
ll ans[310];
ll wow = 0;
ll query(vector <ll> all){
    wow++;
    return query_sample(all);
}
ll cnt_poison = 0;
//0 thuong 1 doc 2 manh
void solve(vector <ll> all){
    if (sz(all) == 1){ans[all.back()]=1;cnt_poison++;return;}
    ll mid = sz(all)/2;
    vector <ll> L;
    vector <ll> R;
    for (ll i = 0;i < mid;i++)L.push_back(all[i]);
    for (ll i = mid;i < sz(all);i ++)R.push_back(all[i]);
    if (query(L)!=sz(L)){
        solve(L);
    }
    else solve(R);
}
void determine_type(int n){
    wow = 0;
    cnt_poison = 0;
    for (ll i = 1;i <= n;i ++)ans[i] = -1;
    deque <ll> pos;
    for (ll i=  1;i <= n;i ++){
        pos.push_back(i);
    }
    ll strong = 0;
    {
        strong = query(vector <ll> (pos.begin(),pos.end()));
    }
    while (sz(pos)&&cnt_poison<30){
        vector <ll> cur;
        while (sz(pos) && sz(cur) < 8){cur.push_back(pos.back());pos.pop_back();}
        vector <ll> all;
        for (ll j= 0 ;j < sz(cur);j ++){
            for (ll k= 0 ;k < MASK(j);k ++)all.push_back(cur[j]);
        }
        ll sus = query(all);
//        for (auto x:all)cout<<x<<' ';
//        cout<<'\n';
        if (sus != sz(all)){
            vector <ll> tmp;
            for (ll j = 0;j < sz(cur);j ++){
                if (BIT(sus,j)){ans[cur[j]] = 2;strong--;}
                else tmp.push_back(cur[j]);
            }
//            for (auto x:tmp)cout<<x<<' ';
//            cout<<'\n';

            cur = tmp;
            solve(cur);
//            for (auto x:cur)cout<<ans[x]<<' ';
//            cout<<'\n';
            bool ok = 0;
            for (auto x:cur){
                if (ans[x] == 1){ok = 1;continue;}
                if (!ok)ans[x] = 0;
                else pos.push_front(x);
            }
        }
//        cout<<sz(pos)<<endl;
    }
//    assert(wow <= 90 + 35);
//    cout<<"WHAT "<<wow<<endl;
	ll poison = -1;
	vector <ll> rem;
    for (ll i = 1;i <= n;i ++){
        if (ans[i] == 1){
            poison = i;
        }
        else{
            if (ans[i] == -1)rem.push_back(i);
        }
    }
//    for (auto x:rem)cout<<x<<' ';
//    cout<<'\n';
    while (sz(rem)&&strong>0){
        vector <ll> cur;
        while (sz(rem) && sz(cur) < 8){cur.push_back(rem.back());rem.pop_back();}
        vector <ll> all;
        for (ll j = 0;j < sz(cur);j ++){
            for (ll k = 0;k < MASK(j);k ++){
                all.push_back(cur[j]);
            }
        }
        all.push_back(poison);
        ll x = query(all);
        for (ll j = 0;j < sz(cur);j ++){
            if (BIT(x,j)){
                ans[cur[j]] = 2;
                strong--;
            }
            else ans[cur[j]] = 0;
        }
    }
    for (ll i = 1;i <= n;i ++)if (ans[i]==-1)ans[i] = 0;
    for (ll i = 1;i <= n;i ++){
        if (ans[i]==0)answer_type(i,'R');
        if (ans[i]==2)answer_type(i,'S');
        if (ans[i]==1)answer_type(i,'T');
    }
}

Subtask #1
59.5 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 6 ms 348 KB Output is correct
3 Partially correct 7 ms 348 KB Partially correct
4 Partially correct 8 ms 348 KB Partially correct
5 Partially correct 7 ms 348 KB Partially correct
6 Partially correct 8 ms 512 KB Partially correct
7 Partially correct 10 ms 348 KB Partially correct
8 Partially correct 9 ms 348 KB Partially correct
9 Partially correct 9 ms 344 KB Partially correct
10 Partially correct 11 ms 348 KB Partially correct
11 Partially correct 8 ms 348 KB Partially correct
12 Correct 6 ms 348 KB Output is correct
13 Partially correct 7 ms 348 KB Partially correct
14 Partially correct 8 ms 348 KB Partially correct
15 Partially correct 8 ms 344 KB Partially correct
16 Partially correct 8 ms 348 KB Partially correct
17 Partially correct 12 ms 348 KB Partially correct
18 Partially correct 9 ms 344 KB Partially correct
19 Partially correct 9 ms 348 KB Partially correct
20 Partially correct 9 ms 512 KB Partially correct
21 Correct 8 ms 344 KB Output is correct
22 Correct 7 ms 348 KB Output is correct
23 Correct 6 ms 348 KB Output is correct
24 Correct 6 ms 348 KB Output is correct
25 Partially correct 7 ms 348 KB Partially correct
26 Partially correct 8 ms 512 KB Partially correct
27 Partially correct 8 ms 600 KB Partially correct
28 Partially correct 8 ms 348 KB Partially correct
29 Partially correct 7 ms 348 KB Partially correct
30 Partially correct 8 ms 348 KB Partially correct
31 Partially correct 12 ms 924 KB Partially correct
32 Partially correct 9 ms 348 KB Partially correct
33 Partially correct 10 ms 348 KB Partially correct
34 Correct 7 ms 348 KB Output is correct
35 Partially correct 8 ms 348 KB Partially correct
36 Correct 2 ms 344 KB Output is correct