Submission #956122

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
956122	2024-04-01T06:20:02 Z	ono_de206	Toxic Gene (NOI23_toxic)	C++17	54.1 / 100	11 ms	516 KB

toxic

#include "toxic.h"
#include<bits/stdc++.h>
using namespace std;
 
#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second
 
//#define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
 
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
void determine_type(int n) {
	vector<int> type(n + 1, 2), sorr, dnow;
	int toxic = 0, samp;
	for(int i = 1; i <= n; i++) {
		dnow.pb(i);
	}
 
	while(dnow.size()) {
		// shuffle(all(dnow), rng);
		vector<int> ask;
		int sz = min((int)dnow.size(), 8);
		for(int i = 0; i < sz; i++) {
			for(int j = 0; j < (1 << i); j++) {
				ask.pb(dnow[i]);
			}
		}
		int ans = query_sample(ask);
		if(ans == ask.size()) {
			for(int i = 0; i < sz; i++) {
				sorr.pb(dnow[0]);
				dnow.erase(dnow.begin());
			}
			continue;
		}
		vector<int> torr;
		for(int i = 0; i < sz; i++) {
			if(ans & (1 << i)) type[dnow[0]] = 0;
			else torr.pb(dnow[0]);
			dnow.erase(dnow.begin());
		}
		int l = 0, r = torr.size() + 1;
		while(r - l > 1) {
			int m = (l + r) / 2;
			ask.clear();
			for(int i = l; i < m; i++) {
				ask.pb(torr[i]);
			}
			int szdn = min((int)sorr.size(), 8);
			for(int i = 0; i < szdn; i++) {
				for(int j = 0; j < (1 << i); j++) {
					ask.pb(sorr[i]);
				}
			}
			ans = query_sample(ask);
			if(ans == ask.size()) {
				l = m;
			} else {
				r = m;
				for(int i = 0; i < szdn; i++) {
					if(ans & (1 << i)) type[sorr[0]] = 0;
					sorr.erase(sorr.begin());
				}
			}
		}
		type[torr[l]] = 1;
		samp = torr[l];
		for(int i = l + 1; i < torr.size(); i++) {
			dnow.pb(torr[i]);
		}
		toxic++;
		if(toxic == 30) {
			for(int x : dnow) {
				sorr.pb(x);
			}
			dnow.clear();
		}
	}
 
	while(sorr.size()) {
		vector<int> ask;
		int sz = min((int)sorr.size(), 8);
		for(int i = 0; i < sz; i++) {
			for(int j = 0; j < (1 << i); j++) {
				ask.pb(sorr[i]);
			}
		}
		ask.pb(samp);
		int ans = query_sample(ask);
		for(int i = 0; i < sz; i++) {
			if(ans & (1 << i)) type[sorr[0]] = 0;
			sorr.erase(sorr.begin());
		}
	}
 
	string str = "STR";
	for(int i = 1; i <= n; i++) {
		answer_type(i, str[type[i]]);
	}
}

Compilation message

toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:40:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |   if(ans == ask.size()) {
      |      ~~~~^~~~~~~~~~~~~
toxic.cpp:67:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if(ans == ask.size()) {
      |       ~~~~^~~~~~~~~~~~~
toxic.cpp:79:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |   for(int i = l + 1; i < torr.size(); i++) {
      |                      ~~^~~~~~~~~~~~~

Subtask #1

54.1 / 100.0

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