Submission #1079121

#TimeUsernameProblemLanguageResultExecution timeMemory
1079121anangoCounting Mushrooms (IOI20_mushrooms)C++17
10 / 100
156 ms856 KiB
#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 = 246; //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 (stderr)

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:47:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |     for (int i=1; i<unknown.size(); i++) {
      |                   ~^~~~~~~~~~~~~~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:110:9: warning: unused variable 'l2' [-Wunused-variable]
  110 |     int l2 = 246; //some space
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...