Submission #357839

#	Time	Username	Problem	Language	Result	Execution time	Memory
357839		doowey	Counting Mushrooms (IOI20_mushrooms)	C++14	80.43 / 100	11 ms	512 KiB

mushrooms

#include <bits/stdc++.h>
#include "mushrooms.h"

using namespace std;

const int N = 20000;

int get_opt(){
    int low = 10000;
    int id = 1;
    for(int k = 1; k <= 300; k ++ ){
        if(k + (N - 2 * k + (k - 1)) / k < low){
            low = k + (N - 2 * k + (k - 1)) / k;
            id = k;
        }
    }
    return id;
}
const int K = get_opt();



int count_mushrooms(int n) {

	int cnt = 1;
    if(n <= 226){
        int cur;
        for(int i = 1; i < n; i ++ ){
            cur = use_machine({0, i});
            if(cur == 0) cnt ++ ;
        }
        return cnt;
    }
    vector<int> q[2];
    q[0].push_back(0);
    int id = 1;
    int A, B, C, D;
    int f;
    int cur;
    while(max(q[0].size(),q[1].size()) <= K){
        if(q[0].size() < 2 && q[1].size() < 2){
            cur = use_machine({0, id});
            if(cur == 0){
                q[0].push_back(id);
            }
            else{
                q[1].push_back(id);
            }
            id ++ ;
        }
        else{
            if(q[0].size() >= 2){
                f = 0;
                A = q[0][0];
                B = q[0][1];
            }
            else{
                f = 1;
                A = q[1][0];
                B = q[1][1];
            }
            C = id;
            D = id + 1;
            id += 2;
            cur = use_machine({A, C, B, D});
            if(cur == 0){
                q[f].push_back(C);
                q[f].push_back(D);
            }
            else if(cur == 1){
                q[f].push_back(C);
                q[f^1].push_back(D);
            }
            else if(cur == 2){
                q[f^1].push_back(C);
                q[f].push_back(D);
            }
            else{
                q[f^1].push_back(C);
                q[f^1].push_back(D);
            }
        }
    }
    int lim = max(q[0].size(), q[1].size());
    int fa = 0;
    if(q[1].size() == lim) fa = 1;
    vector<int> ids;
    int soln = q[0].size();
    int gg;
    int sz;
    int c1;
    for(int i = id; i < n ; i ++ ){
        ids.push_back(i);
        if(ids.size() == lim || i + 1 == n){
            vector<int> qr;
            sz = (int)ids.size();
            for(int t = 0; t < ids.size(); t ++ ){
                qr.push_back(ids[t]);
                qr.push_back(q[fa][t]);
            }
            gg = use_machine(qr);
            if(fa == 0){
                c1 = (gg + 1) / 2;
                soln += sz - c1;
            }
            else{
                soln += (gg + 1) / 2;
            }
            ids.clear();
        }
    }
    return soln;
}

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:40:40: warning: comparison of integer expressions of different signedness: 'const long unsigned int' and 'const int' [-Wsign-compare]
   40 |     while(max(q[0].size(),q[1].size()) <= K){
      |           ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
mushrooms.cpp:86:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |     if(q[1].size() == lim) fa = 1;
      |        ~~~~~~~~~~~~^~~~~~
mushrooms.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |         if(ids.size() == lim || i + 1 == n){
      |            ~~~~~~~~~~~^~~~~~
mushrooms.cpp:97:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |             for(int t = 0; t < ids.size(); t ++ ){
      |                            ~~^~~~~~~~~~~~

• Subtask 1: 80.427 / 100