oj.uz

답안 #940946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
940946 2024-03-08T02:57:04 Z hotboy2703 Toxic Gene (NOI23_toxic) C++17
29.9529 / 100
 8 ms 600 KB 
#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
using ll = int;
using ull = unsigned long long;
using ld = long double;
#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];
//0 thuong 1 doc 2 manh
ll query(ll l,ll r){
    vector <ll> all;
    for (ll i = l;i <= r;i ++)all.push_back(i);
    ll x = query_sample(all);
    return x;
}
void solve(ll l,ll r){
    if (l==r){ans[l]=1;return;}
    ll mid = (l + r) >> 1;
    if (query(l,mid)!=mid-l+1){
        solve(l,mid);
        if (query(mid+1,r)!=r-mid){
            solve(mid+1,r);
        }
    }
    else solve(mid+1,r);
}
void determine_type(int n){
    for (ll i = 1;i <= n;i ++)ans[i] = -1;
	for (ll i = 1;i <= n;i += 8){
        if (query(i,min(i+7,n))!=min(i+7,n) - i + 1)solve(i,min(i+7,n));
	}
	ll poison = -1;
	vector <ll> rem;
    for (ll i = 1;i <= n;i ++){
        if (ans[i] == 1){
            poison = i;
        }
        else{
            rem.push_back(i);
        }
    }
//    for (auto x:rem)cout<<x<<' ';
//    cout<<'\n';
    while (sz(rem)){
        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_sample(all);
        for (ll j = 0;j < sz(cur);j ++){
            if (BIT(x,j)){
                ans[cur[j]] = 2;
            }
            else ans[cur[j]] = 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
29.95294118 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Partially correct 4 ms 348 KB Partially correct
3 Partially correct 4 ms 344 KB Partially correct
4 Partially correct 5 ms 348 KB Partially correct
5 Partially correct 5 ms 500 KB Partially correct
6 Partially correct 5 ms 344 KB Partially correct
7 Partially correct 5 ms 348 KB Partially correct
8 Partially correct 5 ms 344 KB Partially correct
9 Partially correct 5 ms 344 KB Partially correct
10 Partially correct 5 ms 348 KB Partially correct
11 Partially correct 6 ms 500 KB Partially correct
12 Partially correct 4 ms 348 KB Partially correct
13 Partially correct 4 ms 348 KB Partially correct
14 Partially correct 5 ms 348 KB Partially correct
15 Partially correct 5 ms 344 KB Partially correct
16 Partially correct 5 ms 600 KB Partially correct
17 Partially correct 5 ms 348 KB Partially correct
18 Partially correct 5 ms 348 KB Partially correct
19 Partially correct 6 ms 504 KB Partially correct
20 Partially correct 5 ms 348 KB Partially correct
21 Partially correct 5 ms 348 KB Partially correct
22 Partially correct 5 ms 348 KB Partially correct
23 Partially correct 4 ms 504 KB Partially correct
24 Correct 8 ms 348 KB Output is correct
25 Correct 5 ms 348 KB Output is correct
26 Correct 4 ms 348 KB Output is correct
27 Correct 5 ms 348 KB Output is correct
28 Correct 4 ms 348 KB Output is correct
29 Correct 4 ms 344 KB Output is correct
30 Correct 7 ms 600 KB Output is correct
31 Correct 6 ms 348 KB Output is correct
32 Correct 4 ms 348 KB Output is correct
33 Correct 4 ms 348 KB Output is correct
34 Partially correct 5 ms 348 KB Partially correct
35 Partially correct 7 ms 344 KB Partially correct
36 Partially correct 1 ms 348 KB Partially correct