Submission #1079121

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079121		anango	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	156 ms	856 KiB

mushrooms

#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
      |         ^~

• Subtask 1: 10 / 100