| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 886166 | vjudge1 | Toxic Gene (NOI23_toxic) | C++17 | 8 ms | 600 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define LOGN 8
void query(vector<int> &v, vector<int> &ans){
if (v.size() == 1){
ans.pb(v.back());
return;
}
int t = -1;
for (int i = 2; i >= 0; i--){
int tmp = t + (1<<i);
if (tmp + 1 < v.size()){
vector<int> gh;
for (int i = 0; i <= tmp; i++) gh.pb(v[i]);
if (query_sample(gh) == gh.size()) t = tmp;
}
}
t++;
ans.pb(v[t]);
vector<int> nv;
for (int i = t + 1; i < v.size(); i++) nv.pb(v[i]);
if (query_sample(nv) != nv.size()) query(nv, ans);
}
void determine_type(int n){
vector<int> type(n + 5);
int t = 1;
for (int i = LOGN; i >= 0; i--){
int tmp = t + (1<<i);
if (tmp <= n){
vector<int> v;
for (int i = 1; i <= tmp; i++) v.pb(i);
if (query_sample(v) == v.size()) t = tmp;
}
}
vector<int> v;
if (t == 1){
v.pb(t);
if (query_sample(v) != 0) t++;
}
else{
t++;
}
//cout<<q[current_tc]<<sp;
//cout<<t<<endl;
type[t] = 1;
for (int i = 1; i <= n; i += 8){
vector<int> v;
int e = min(8, n - i + 1);
for (int j = 0; j < e; j++){
for (int k = 1; k <= (1<<j); k++)
v.pb(i + j);
}
if (t < i || t >= i + e) v.pb(t);
int sum = (1<<e) - 1;
int res = query_sample(v);
//for (auto i : v) cout<<i<<sp;
//cout<<": "<<res<<endl;
for (int j = 0; j < e; j++){
if ((res & (1<<j))) type[i + j] = 2;
}
}
//cout<<q[current_tc]<<sp;
for (int i = 1; i <= n; i += 8){
vector<int> v;
for (int j = 0; j < min(8, n - i + 1); j++){
v.pb(i + j);
}
int res = query_sample(v);
if (res != v.size()){
vector<int> ans;
query(v, ans);
for (auto i : ans) type[i] = 1;
}
}
//cout<<q[current_tc]<<endl;
for (int i = 1; i <= n; i++){
if (type[i] == 0) answer_type(i, 'R');
else if (type[i] == 1) answer_type(i, 'T');
else answer_type(i, 'S');
}
}
/*
namespace {
static void wrong_answer(){
printf("%d\n",-1);
//exit(0);
}
static int tc, current_tc, N, batchsize = 300, qlimit = 600;
static int q[105];
static char answer[105][305];
static char participant_type[105][305];
}
int query_sample(vector<int> species){
if (species.size() > batchsize){
cout<<"size exceeded"<<endl;
wrong_answer();
}
q[current_tc]++;
if (q[current_tc] > qlimit){
cout<<"query limit exceeded"<<endl;
wrong_answer();
}
bool has_toxic = false;
int reg = 0, strong = 0;
for (int i = 0; i < (int) species.size(); ++i){
if (species[i] < 1 || species[i] > N){
cout<<"specie id invalid"<<endl;
wrong_answer();
}
char tp = answer[current_tc][species[i]];
if (tp == 'T'){
has_toxic = true;
}
if (tp == 'R'){
reg++;
}
if (tp == 'S'){
strong++;
}
}
if (has_toxic) return strong;
else return reg + strong;
}
void answer_type(int x, char c){
//cout<<c<<sp;
if (x < 1 || x > N) wrong_answer();
if (c != 'T' && c != 'R' && c != 'S') wrong_answer();
participant_type[current_tc][x] = c;
if (participant_type[current_tc][x] != answer[current_tc][x]) wrong_answer();
}
int main(){
fileio();
assert(2 == scanf("%d %d\n",&tc,&N));
for (int t = 1; t <= tc; ++t){
assert(1 == scanf("%s",answer[t]));
for (int i = N; i >= 1; --i){
answer[t][i] = answer[t][i-1];
}
answer[t][0] = 'X';
for (int i = 1; i <= N; ++i){
participant_type[t][i] = 'X';
}
}
for (int t = 1; t <= tc; ++t){
current_tc = t;
q[current_tc] = 0;
determine_type(N);
for (int i = 1; i <= N; ++i){
if (participant_type[current_tc][i] != answer[current_tc][i]) wrong_answer();
}
}
for (int t = 1; t <= tc; ++t){
printf("%d\n",q[t]);
}
return 0;
}*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||