#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;
void prv(vector<int> v) {
for (auto i:v) {
cout << i <<" ";
}
cout << endl;
}
vector<int> listrange(int l, int r) {
vector<int> ans;
for (int i=l; i<=r; i++) {
ans.push_back(i);
}
return ans;
}
int simple_check(int i1, int i2) {
//return whether i1!=i2
return use_machine({i1,i2});
}
pair<int,int> double_check(pair<int,int> known, int known_type, pair<int,int> unknown) {
//returns the types of two values by testing them against the known
int ct = use_machine({unknown.first,known.first,unknown.second,known.second});
if (known_type==1) {
ct=3-ct;
}
// return {known_type^simple_check(known.first,unknown.first),known_type^simple_check(known.second,unknown.second)};
return {ct%2,ct/2};
}
pair<int,int> simple_count(vector<int> known, int known_type, vector<int> unknown) {
//return {type of first unknown, count of A among the rest of the unknowns}
assert(unknown.size()<=known.size());
assert(unknown.size()>0);
vector<int> m={unknown[0]};
for (int i=0; i<known.size(); i++) {
m.push_back(known[i]);
if (i+1<unknown.size()) {
m.push_back(unknown[i+1]);
}
}
int c1 = 0;
/*for (int i=1; i<unknown.size(); i++) {
c1+=simple_check(0,unknown[i]);
}
return {simple_check(0,unknown[0]),c1};*/
//prv(m);
int ct = use_machine(m);
if (known_type==1) {
ct = ((int)2*unknown.size())-1-ct;
}
return {ct%2,ct/2};
}
int count_mushrooms(int n) {
/*std::vector<int> m;
for (int i = 0; i < n; i++)
m.push_back(i);
int c1 = use_machine(m);
m = {0, 1};
int c2 = use_machine(m);*/
//suppose we know 100 As
//given a group of at most 99 mushrooms, we can easily count the number of As
//by inserting them in between the previous As
//and each B will increase the number of differing adjacent pairs by 1
//we can even insert something before all the As, and we have full knowledge of what this is
//since all the other deltas will be even, but if this is B then the entire delta will be odd
//since the B contributes 1 to the result
//thus this gives a k+n/k solution
//like 632+316 queries if we naively find the group of As
//maybe, we can increase the size of the segment gradually
//starting with just one A
//we can put 1 before the A to test it
//and keep a segment of As and a segment of Bs
//and use the longer one each time to test, and every time we gain info of one letter as well
//worst case is if it keeps alternating As and Bs
//then we need upto 631 queries
//constraints misread
//n=20k not 100k
//ok so the first method uses 141*3 queries
//second uses like 284 queries, decent
//ok but we can do something a bit different
//suppose we know 2 As (or Bs, that takes like 4 queries or something tiny)
//then you can explicitly test 2 characters by putting MAGA where M and G are the 2 testing characters
//since G increases it by 2 if B and M increases it by 1 if B
//so what you can do is use 100 queries to find out 200 letters
//then put all the As together and use the first method
//that is, unfortunately, still 284 queries even when we optimise it using 141 queries in the first stage
//somehow combine these methods
//start by explicitly testing 2 characters each time upto some limit l1 queries
//then keep doing the normal test with 1 new character each time
//manual binary search to find optimal l1
//results: l1=80 and l2=244
//that's like 90 points
//just implement this forget about 100
int l1 = 80;
if (n<l1*2+20) {
int ct=0;
for (int i=1; i<n; i++) {
ct+=simple_check(0,i);
}
return n-ct;
}
int l2 = 245; //some space
//first do 4 queries to find AA
vector<int> known_a={0};
vector<int> known_b;
int ct = 0;
int pointer = 1;
while (pointer<3) {
int k = simple_check(0,pointer);
if (k) {
known_b.push_back(pointer);
}
else {
known_a.push_back(pointer);
}
pointer++;
}
assert(known_a.size()>=2 || known_b.size()>=2);
for (int i=0; i<l1; i++) {
pair<int,int> to_use;
int type;
if (known_a.size()>=2) {
type = 0;
to_use = {known_a[0],known_a[1]};
}
else if (known_b.size()>=2) {
type = 1;
to_use = {known_b[0],known_b[1]};
}
else {
assert(false);
}
pair<int,int> dc = double_check(to_use,type,{pointer,pointer+1});
if (dc.first==0) {
known_a.push_back(pointer);
}
else {
known_b.push_back(pointer);
}
pointer++;
if (dc.second==0) {
known_a.push_back(pointer);
}
else {
known_b.push_back(pointer);
}
pointer++;
}
int its = 0;
while (pointer<n) {
int ctype = 0;
its++;
if (known_a.size()<known_b.size()) {
ctype = 1;
}
/*if (ctype==0) {
int np = min(n-1,pointer-1+(int)known_a.size());
for (int i:listrange(pointer+1,np)) {
ct+=simple_check(known_a[0],i);
}
if (simple_check(known_a[0],pointer)) {
known_b.push_back(pointer);
}
else {
known_a.push_back(pointer);
}
pointer=np+1;
}
else {
ct+=1^simple_check(known_b[0],pointer);
pointer++;
}
*/
if (ctype==0) {
int np = min(n-1,pointer-1+(int)known_a.size());
pair<int,int> counts = simple_count(known_a,0,listrange(pointer,np));
if (counts.first==0) {
known_a.push_back(pointer);
}
else {
known_b.push_back(pointer);
}
ct+=counts.second;
pointer = np+1;
}
else if (ctype==1) {
int np = min(n-1,pointer-1+(int)known_b.size());
pair<int,int> counts = simple_count(known_b,1,listrange(pointer,np));
if (counts.first==0) {
known_a.push_back(pointer);
}
else {
known_b.push_back(pointer);
}
ct+=counts.second;
pointer = np+1;
}
}
ct+=known_b.size();
return n-ct;
}
Compilation message
mushrooms.cpp: In function 'std::pair<int, int> simple_count(std::vector<int>, int, std::vector<int>)':
mushrooms.cpp:40:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (int i=0; i<known.size(); i++) {
| ~^~~~~~~~~~~~~
mushrooms.cpp:42:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if (i+1<unknown.size()) {
| ~~~^~~~~~~~~~~~~~~
mushrooms.cpp:46:9: warning: unused variable 'c1' [-Wunused-variable]
46 | int c1 = 0;
| ^~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:110:9: warning: unused variable 'l2' [-Wunused-variable]
110 | int l2 = 245; //some space
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Correct |
0 ms |
344 KB |
Output is correct |
| 3 |
Correct |
0 ms |
344 KB |
Output is correct |
| 4 |
Correct |
0 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
344 KB |
Output is correct |
| 6 |
Correct |
1 ms |
440 KB |
Output is correct |
| 7 |
Correct |
3 ms |
344 KB |
Output is correct |
| 8 |
Correct |
3 ms |
468 KB |
Output is correct |
| 9 |
Correct |
6 ms |
344 KB |
Output is correct |
| 10 |
Correct |
3 ms |
344 KB |
Output is correct |
| 11 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 12 |
Correct |
4 ms |
600 KB |
Output is correct |
| 13 |
Correct |
3 ms |
468 KB |
Output is correct |
| 14 |
Correct |
2 ms |
704 KB |
Output is correct |
| 15 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 16 |
Partially correct |
5 ms |
484 KB |
Output is partially correct |
| 17 |
Correct |
3 ms |
344 KB |
Output is correct |
| 18 |
Correct |
5 ms |
344 KB |
Output is correct |
| 19 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 20 |
Correct |
4 ms |
472 KB |
Output is correct |
| 21 |
Correct |
3 ms |
344 KB |
Output is correct |
| 22 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 23 |
Correct |
3 ms |
344 KB |
Output is correct |
| 24 |
Correct |
2 ms |
344 KB |
Output is correct |
| 25 |
Partially correct |
4 ms |
468 KB |
Output is partially correct |
| 26 |
Partially correct |
4 ms |
472 KB |
Output is partially correct |
| 27 |
Partially correct |
4 ms |
456 KB |
Output is partially correct |
| 28 |
Partially correct |
5 ms |
472 KB |
Output is partially correct |
| 29 |
Partially correct |
6 ms |
612 KB |
Output is partially correct |
| 30 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 31 |
Partially correct |
6 ms |
456 KB |
Output is partially correct |
| 32 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 33 |
Partially correct |
4 ms |
448 KB |
Output is partially correct |
| 34 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 35 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 36 |
Partially correct |
6 ms |
344 KB |
Output is partially correct |
| 37 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 38 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 39 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 40 |
Partially correct |
5 ms |
604 KB |
Output is partially correct |
| 41 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 42 |
Partially correct |
4 ms |
444 KB |
Output is partially correct |
| 43 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 44 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 45 |
Partially correct |
6 ms |
456 KB |
Output is partially correct |
| 46 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 47 |
Partially correct |
4 ms |
600 KB |
Output is partially correct |
| 48 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 49 |
Partially correct |
3 ms |
456 KB |
Output is partially correct |
| 50 |
Partially correct |
4 ms |
448 KB |
Output is partially correct |
| 51 |
Partially correct |
5 ms |
480 KB |
Output is partially correct |
| 52 |
Partially correct |
5 ms |
608 KB |
Output is partially correct |
| 53 |
Partially correct |
4 ms |
600 KB |
Output is partially correct |
| 54 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 55 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 56 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 57 |
Partially correct |
3 ms |
344 KB |
Output is partially correct |
| 58 |
Partially correct |
4 ms |
476 KB |
Output is partially correct |
| 59 |
Partially correct |
6 ms |
600 KB |
Output is partially correct |
| 60 |
Partially correct |
4 ms |
600 KB |
Output is partially correct |
| 61 |
Partially correct |
4 ms |
344 KB |
Output is partially correct |
| 62 |
Correct |
0 ms |
344 KB |
Output is correct |
| 63 |
Correct |
0 ms |
344 KB |
Output is correct |
| 64 |
Correct |
0 ms |
344 KB |
Output is correct |
| 65 |
Correct |
0 ms |
344 KB |
Output is correct |
| 66 |
Correct |
0 ms |
344 KB |
Output is correct |
| 67 |
Correct |
0 ms |
344 KB |
Output is correct |
| 68 |
Correct |
0 ms |
344 KB |
Output is correct |
| 69 |
Correct |
0 ms |
344 KB |
Output is correct |
| 70 |
Correct |
0 ms |
344 KB |
Output is correct |
| 71 |
Correct |
0 ms |
344 KB |
Output is correct |
| 72 |
Correct |
0 ms |
344 KB |
Output is correct |
| 73 |
Correct |
0 ms |
344 KB |
Output is correct |
| 74 |
Correct |
0 ms |
344 KB |
Output is correct |
| 75 |
Correct |
0 ms |
344 KB |
Output is correct |
| 76 |
Correct |
0 ms |
424 KB |
Output is correct |
| 77 |
Correct |
1 ms |
344 KB |
Output is correct |
| 78 |
Correct |
0 ms |
344 KB |
Output is correct |
| 79 |
Correct |
0 ms |
344 KB |
Output is correct |
| 80 |
Correct |
0 ms |
344 KB |
Output is correct |
| 81 |
Correct |
0 ms |
344 KB |
Output is correct |
| 82 |
Correct |
1 ms |
344 KB |
Output is correct |
| 83 |
Correct |
0 ms |
344 KB |
Output is correct |
| 84 |
Correct |
1 ms |
344 KB |
Output is correct |
| 85 |
Correct |
0 ms |
344 KB |
Output is correct |
| 86 |
Correct |
0 ms |
344 KB |
Output is correct |
| 87 |
Correct |
1 ms |
344 KB |
Output is correct |
| 88 |
Correct |
1 ms |
344 KB |
Output is correct |
| 89 |
Correct |
0 ms |
344 KB |
Output is correct |
| 90 |
Correct |
0 ms |
344 KB |
Output is correct |
| 91 |
Correct |
0 ms |
344 KB |
Output is correct |
