Submission #413853

#	Time	Username	Problem	Language	Result	Execution time	Memory
413853		ivan24	버섯 세기 (IOI20_mushrooms)	C++14	91.87 / 100	11 ms	316 KiB

mushrooms

#include "mushrooms.h"
 
#include <bits/stdc++.h>
using namespace std;
using ll = int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second
 
class Solver{
private:
    ll n;
    vvi known;
    ll cnt[2];
 
    void typeZeroQuery (ll x){
        ll res = use_machine(vi{0,x});
        known[res].push_back(x);
    }
 
    void typeOneQuery(ll x1, ll x2){
        ll curType = 0;
        if (2 > known[0].size()) curType = 1;
 
        vi v = {known[curType][0],x1,known[curType][1],x2};
 
        ll res = use_machine(v);
 
        if (res & 2){
            known[1-curType].push_back(x1);
        }else{
            known[curType].push_back(x1);
        }
 
        if (res & 1){
            known[1-curType].push_back(x2);
        }else{
            known[curType].push_back(x2);
        }
    }
 
    ll typeTwoQuery (ll sptr){
        vi queryAr;
        ll curType = 0;
 
        ll ogsptr = sptr;
 
        if (known[curType].size() < known[1-curType].size()){
            curType = 1-curType;
        }
 
        for (ll i = 0; known[curType].size() > i && n > sptr; i++){
            queryAr.push_back(known[curType][i]);
            queryAr.push_back(sptr++);
        }
 
        ll res = use_machine(queryAr);
        ll mod2 = res%2;
        res = (res+1)/2;
 
        cnt[1-curType] += res;
        cnt[curType] += (sptr-ogsptr) - res;
 
        if (mod2 == 0){
            cnt[curType]--;
            known[curType].push_back(sptr-1);
        }else{
            cnt[1-curType]--;
            known[1-curType].push_back(sptr-1);
        }
 
        return sptr;
    }
 
public:
    Solver(ll n): n(n){
 
    }
 
    ll solve(){
 
        cnt[0] = cnt[1] = 0;
 
        known.assign(2,vi());
        known[0].push_back(0);
        ll ptr = 1;
 
        for (; 3 > ptr && n > ptr;){
            typeZeroQuery(ptr++);
        }
 
        for (;2*n > ptr*ptr && n > ptr;){
            typeOneQuery(ptr,ptr+1);
            ptr += 2;
        }
 
        for (;n>ptr;){
            ptr = typeTwoQuery(ptr);
        }
 
        return known[0].size()+cnt[0];
    }
};
 
int count_mushrooms(int n) {
	Solver mySolver(n);
	return mySolver.solve();
}

Compilation message (stderr)

mushrooms.cpp: In member function 'll Solver::typeTwoQuery(ll)':
mushrooms.cpp:56:46: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'int'} [-Wsign-compare]
   56 |         for (ll i = 0; known[curType].size() > i && n > sptr; i++){
      |                        ~~~~~~~~~~~~~~~~~~~~~~^~~

• Subtask 1: 91.8699 / 100