Submission #1079065

#TimeUsernameProblemLanguageResultExecution timeMemory
1079065anango버섯 세기 (IOI20_mushrooms)C++17
10 / 100
136 ms596 KiB
#include "mushrooms.h" #include <bits/stdc++.h> using namespace std; 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 {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 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 if (n<30000) { int ct=0; for (int i=1; i<n; i++) { ct+=simple_check(0,i); } return n-ct; } int l1 = 80; int l2 = 246; //some space //first do 4 queries to find AA int ans = 0; return n-ans; }

Compilation message (stderr)

mushrooms.cpp: In function 'std::pair<int, int> simple_count(std::vector<int>, int, std::vector<int>)':
mushrooms.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for (int i=0; i<known.size(); i++) {
      |                   ~^~~~~~~~~~~~~
mushrooms.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         if (i+1<unknown.size()) {
      |             ~~~^~~~~~~~~~~~~~~
mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:87:9: warning: unused variable 'l1' [-Wunused-variable]
   87 |     int l1 = 80;
      |         ^~
mushrooms.cpp:88:9: warning: unused variable 'l2' [-Wunused-variable]
   88 |     int l2 = 246; //some space
      |         ^~
#Verdict Execution timeMemoryGrader output
Fetching results...