| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1079126 | anango | 비스킷 담기 (IOI20_biscuits) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}