Submission #849345

#	Time	Username	Problem	Language	Result	Execution time	Memory
849345		YassineBenYounes	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	1 ms	600 KiB

mushrooms

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<int, int>, null_type, less<pair<int, int>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
using namespace std;

void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}

typedef long long ll;
////////////////////Only Clear Code//////////////////////////

#define vi vector<int>
#define pb push_back
const int mx = 1e3 + 9;
int k = 0;

vi res = {0, 0, 0};

int use_machine(vi x);

int count_mushrooms(int n){
    int k = 4;
    vi one;
    one.pb(0);
    //int bs = sqrt(n);
    while(one.size() < k){
        while(one.size() < k){
            int o = one.back()+1;
            if(o >= n)break;
            vi v = {one.back(), o};
            if(use_machine(v) == 1)break;
            one.pb(o);
        }
        if(one.back() == n-1){
            assert(false);
            return one.size();
        }
        if(one.size() == k)break;
        int l = one.back()+1, r = n-1;
        int ans = -1;
        while(l <= r){
            int md = (l+r)/2;
            vi v;
            v.pb(one.back());
            for(int i = one.back()+1; i <= md;i++){
                v.pb(i);
            }
            int x = use_machine(v);
            if(x == 1){
                l = md+1;
            }
            else{
                ans = md;
                r = md-1;
            }
        }
        if(ans == -1){
            assert(false);
            return one.size();
        }
        one.pb(ans);
    }
    int ans = one.size();
    vi cur;
    k = one.size()-1;
    for(int i = one.back()+1; i < n;i++){
        cur.pb(i);
        if(cur.size() == k){
            vi v;
            for(int j = 0;j < cur.size();j++){
                v.pb(one[j]);
                v.pb(cur[j]);
            }
            v.pb(one.back());
            ans += cur.size() - use_machine(v)/2;
            cur.clear();
        }
    }
    if(cur.size() != 0){
        vi v;
        for(int j = 0;j < cur.size();j++){
            v.pb(one[j]);
            v.pb(cur[j]);
        }
        v.pb(one.back());
        ans += cur.size() - use_machine(v)/2;
        cur.clear();
    }
    assert(false);
    return ans;
}
/*
int main(){
    init();
    cout << count_mushrooms(3) << endl;
    cout << k << endl;
}*/

/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:35:22: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     while(one.size() < k){
      |           ~~~~~~~~~~~^~~
mushrooms.cpp:36:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |         while(one.size() < k){
      |               ~~~~~~~~~~~^~~
mushrooms.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |         if(one.size() == k)break;
      |            ~~~~~~~~~~~^~~~
mushrooms.cpp:77:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |         if(cur.size() == k){
      |            ~~~~~~~~~~~^~~~
mushrooms.cpp:79:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             for(int j = 0;j < cur.size();j++){
      |                           ~~^~~~~~~~~~~~
mushrooms.cpp:90:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int j = 0;j < cur.size();j++){
      |                       ~~^~~~~~~~~~~~
mushrooms.cpp: In function 'void init()':
mushrooms.cpp:11:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mushrooms.cpp:13:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 100