Submission #886132

#	Time	Username	Problem	Language	Result	Execution time	Memory
886132		vjudge1	Toxic Gene (NOI23_toxic)	C++17	36.68 / 100	16 ms	600 KiB

toxic

#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;

inline set<int> whodied(vector<int> a) {
	if(a.size()>8) return {};
	vector<int> b;
	for(int i=0; i<a.size(); i++) {
		for(int j=0; j<(1<<i); j++) b.push_back(a[i]);
	}
	int c = query_sample(b);
	c = b.size()-c;
	set<int> ans;
	for(int i=0; i<8; i++) if(c&(1<<i)) ans.insert(a[i]);
	return ans;
}

inline set<int> whodied(vector<int> a, int b) {
	if(a.size()>8) return {};
	vector<int> d;
	for(int i=0; i<a.size(); i++) {
		for(int j=0; j<(1<<i); j++) d.push_back(a[i]);
	}
	d.push_back(b);
	int c = query_sample(d);
	c = d.size()-c;
	c--;
	set<int> ans;
	for(int i=0; i<8; i++) if(c&(1<<i)) ans.insert(a[i]);
	return ans;
} 

void determine_type(int n){
	set<int> strong, normal, toxic;
	vector<int> killable, killable4, killable2;

	queue<pair<int,int>> later;
	for(int i=1; i<=n; i+=8) {
		vector<int> cur;
		for(int j=i; j<min(i+8, n+1); j++) cur.push_back(j);
		set<int> curdead = whodied(cur);
		if(curdead.size()==0) {
			later.push({i, min(i+8-1, n)});
			continue;
		}
		for(int j=i; j<min(i+8, n+1); j++) {
			if(curdead.count(j)) killable.push_back(j);
			else strong.insert(j);
		}
	}
	
	for(int i=0; i<killable.size(); i+=4) {
		vector<int> cur;
		for(int j=i; j<min(i+4, (int)killable.size()); j++) cur.push_back(killable[j]);
		set<int> curdead = whodied(cur);
		if(curdead.size()==0) {
			for(int j=i; j<min(i+4, (int)killable.size()); j++) {
				normal.insert(killable[j]);
			}
		}
		else {
			for(int j=i; j<min(i+4, (int)killable.size()); j++) killable4.push_back(killable[j]);
		}
	}

	for(int i=0; i<killable4.size(); i+=2) {
		vector<int> cur;
		for(int j=i; j<min(i+2, (int)killable4.size()); j++) cur.push_back(killable4[j]);
		set<int>curdead = whodied(cur);
		if(curdead.size()==0) {
			for(int j=i; j<min(i+2, (int)killable4.size()); j++) {
				normal.insert(killable4[j]);
			}
		}
		else {
			for(int j=i; j<min(i+2, (int)killable4.size()); j++) killable2.push_back(killable4[j]);
		}
	}

	for(int i=0; i<killable2.size(); i++) {
		vector<int> cur(1, killable2[i]);
		set<int> curdead = whodied(cur);
		if(curdead.size()==0) normal.insert(killable2[i]);
		else toxic.insert(killable2[i]);
	}

	while(!later.empty()) {
		int l = later.front().first;
		int r = later.front().second;
		later.pop();
		vector<int> cur;
		for(int i=l; i<=r; i++) cur.push_back(i);
		set<int> curdead = whodied(cur, *toxic.begin());
		for(int i=l; i<=r; i++) {
			if(curdead.count(i)) normal.insert(i);
			else strong.insert(i);
		}
	}

	for(auto x:strong) answer_type(x, 'S');
	for(auto x:normal) answer_type(x, 'R');
	for(auto x:toxic) answer_type(x, 'T');
}

Compilation message (stderr)

toxic.cpp: In function 'std::set<int> whodied(std::vector<int>)':
toxic.cpp:8:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |  for(int i=0; i<a.size(); i++) {
      |               ~^~~~~~~~~
toxic.cpp: In function 'std::set<int> whodied(std::vector<int>, int)':
toxic.cpp:21:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i=0; i<a.size(); i++) {
      |               ~^~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |  for(int i=0; i<killable.size(); i+=4) {
      |               ~^~~~~~~~~~~~~~~~
toxic.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for(int i=0; i<killable4.size(); i+=2) {
      |               ~^~~~~~~~~~~~~~~~~
toxic.cpp:80:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |  for(int i=0; i<killable2.size(); i++) {
      |               ~^~~~~~~~~~~~~~~~~

• Subtask 1: 36.68235294 / 100