oj.uz

답안 #886118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886118 2023-12-11T13:26:01 Z vjudge1 Toxic Gene (NOI23_toxic) C++17
3.99231 / 100
 4 ms 600 KB 
#include "toxic.h"
#include <bits/stdc++.h>

#define lli long long int
#define MP make_pair
#define REP(i,n) for(int (i); (i)<(n); (i)++)
#define pb push_back

const int N = 305;

const int MOD = 1e9+7;
constexpr lli INF = 1e17;
using namespace std;

void fastio() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

vector<char> typ(N, 'X');
int ex;
void solve(vector<int> &cur, int cnt) {
	int sz = cur.size();
	if(!sz) return;
	if(sz == 1) {
		if(cnt) {
			typ[cur[0]] = 'S';
		}
		else {
			typ[cur[0]] = 'R';
		}
		return;
	}
	
	if(cnt == sz) {
		for(auto c : cur) {
			typ[c] = 'S';
		}
		return;
	}
	if(cnt == 0) {
		for(auto c : cur) {
			typ[c] = 'R';
		}
		return;
	}
	vector<int> nw;
	for(int i = 0; i<sz/2; i++) {
		nw.pb(cur.back());
		cur.pop_back();
	}
	cur.pb(ex);
	int nxt = query_sample(cur);
	cur.pop_back();
	solve(cur, nxt);
	solve(nw, cnt - nxt);
	
}
void determine_type(int n){
	

	vector<int> nont;

	for(int i = 1 ;i<=n; i++) {
		if(!query_sample({i})) {
			typ[i] = 'T';
			ex = i;
		}
		else {
			nont.pb(i);
		}
	}	
	shuffle(nont.begin(), nont.end(), rng);
	nont.pb(ex);
	int cnt = query_sample(nont);
	nont.pop_back();
	solve(nont, cnt); 
	for(int i = 1; i<=n; i++) {
		answer_type(i, typ[i]);
	}
}

Subtask #1
3.99230769 / 100.0

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