| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 886095 |
2023-12-11T13:03:17 Z |
vjudge1 |
Toxic Gene (NOI23_toxic) |
C++17 |
|
1000 ms |
248276 KB |
#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);
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--;
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, i+8-1});
continue;
}
for(int j=i; i<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<i+4; j++) cur.push_back(killable[j]);
set<int> curdead = whodied(cur);
if(curdead.size()==0) {
for(int j=i; j<i+4; j++) {
normal.insert(killable[j]);
}
}
else {
for(int j=i; j<i+4; j++) killable4.push_back(killable[j]);
}
}
for(int i=0; i<killable4.size(); i+=2) {
vector<int> cur;
for(int j=i; j<i+2; j++) cur.push_back(killable4[j]);
set<int>curdead = whodied(cur);
if(curdead.size()==0) {
for(int j=i; j<i+2; j++) {
normal.insert(killable4[j]);
}
}
else {
for(int j=i; j<i+2; 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
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:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0; i<a.size(); i++) {
| ~^~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0; i<killable.size(); i+=4) {
| ~^~~~~~~~~~~~~~~~
toxic.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
64 | for(int i=0; i<killable4.size(); i+=2) {
| ~^~~~~~~~~~~~~~~~~
toxic.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | for(int i=0; i<killable2.size(); i++) {
| ~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1068 ms |
248276 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
