Submission #1079065

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079065		anango	Counting Mushrooms (IOI20_mushrooms)	C++17	10 / 100	136 ms	596 KiB

mushrooms

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

• Subtask 1: 10 / 100