Submission #899616

#	Time	Username	Problem	Language	Result	Execution time	Memory
899616		hihihahaa	Counting Mushrooms (IOI20_mushrooms)	C++17	92.62 / 100	6 ms	728 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define forinc(i,a,b) for(int i=a;i<=b;i++)
#define fordec(i,a,b) for(int i=a;i>=b;i--)
#define fi first
#define se second
#define pb push_back
//#define int long long
#define ll __int128
#define mp make_pair
#define nn "\n"
#define fasty ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
 
int in,res,debug,cnt,len,k,n;
int a[1000000];
/*
int use_machine(vector<int> x){
    cnt++; len+=x.size(); if(len>100000) cout << "wa2 " << len << nn;
    int ans=0;
    //forinc(i,0,x.size()-1) forinc(j,i+1,x.size()-1) if(x[i]==x[j]) cout << "wa1" << nn;
    forinc(i,1,x.size()-1){
        if(a[x[i]]!=a[x[i-1]]) ans++;
    } 
    return ans;
}
*/

 
int count_mushrooms(int n){
    /*
    cost=k+2*i
    n=2*(k+k+k+1+...+(k+i-1));
    ~ (2*k+i)*i
    3*n <= (2*k+i)*(3*i) <= (k+2*i)^2 => k=sqrt(n/3)
    */
    bool stt; int cut=(int)(sqrt(n/3)); 
    vector<int> A, B; A.pb(0);
    int pt=1;
    // step 1;
    for(;pt<n;pt++){
        vector<int> out{0,pt}; debug=2; res=use_machine(out);
        if(res) B.pb(pt);
        else A.pb(pt);
        if(A.size()==2){
            stt=1; pt++; break;
        } 
        if(B.size()==2){
            stt=0; pt++; break;
        }
    }
    //cout << pt << " " << 1 << nn;
    // step 2 
    if(n>10){
        if(stt){
            for(;pt<n;pt+=2){
                vector<int> out{A[0],pt,A[1],pt+1}; debug=4; res=use_machine(out);
                if(res==0){
                    A.pb(pt); A.pb(pt+1);
                } else if(res==1){
                    A.pb(pt); B.pb(pt+1);
                } else if(res==2){
                    B.pb(pt); A.pb(pt+1);
                } else{
                    B.pb(pt); B.pb(pt+1);
                } if(A.size()>=cut){
                    stt=1; pt+=2; break;
                } if(B.size()>=cut){
                    stt=0; pt+=2; break;
                }
            }
        }
        else{
            for(;pt<n;pt+=2){
                vector<int> out{B[0],pt,B[1],pt+1}; debug=4; res=use_machine(out);
                if(res==0){
                    B.pb(pt); B.pb(pt+1);
                } else if(res==1){
                    B.pb(pt); A.pb(pt+1);
                } else if(res==2){
                    A.pb(pt); B.pb(pt+1);
                } else{
                    A.pb(pt); A.pb(pt+1);
                } if(A.size()>=cut){
                    pt+=2; break;
                } if(B.size()>=cut){
                    pt+=2; break;
                }
            }
        }
    }
    //cout << pt << " " << 2 << nn;
    // step 3 
    int ans=A.size();
    while(pt<n){
        if(A.size()>B.size()){
            k=A.size();
            vector<int> out; debug=2*min(k,n-pt); forinc(i,0,debug/2-1){
                out.pb(A[i]);
                out.pb(pt);
                pt++;
            } 
            res=use_machine(out);
            ans+=debug/2-(res+1)/2; 
            if(res%2) B.pb(pt-1);
            else A.pb(pt-1);
        }
        else{
            k=B.size();
            vector<int> out; debug=2*min(k,n-pt); forinc(i,0,debug/2-1){
                out.pb(B[i]);
                out.pb(pt);
                pt++;
            } 
            res=use_machine(out);
            ans+=(res+1)/2; 
            if(res%2) A.pb(pt-1);
            else B.pb(pt-1);
        }
    }
    //cout << pt << " " << 3 << nn;
    return ans;
}
/*
signed main(){
    
    std::random_device rd;  // a seed source for the random number engine
    std::mt19937 gen(rd()); // mersenne_twister_engine seeded with rd()
    std::uniform_int_distribution<> distrib(0,1);
    std::uniform_int_distribution<> d(18000,20000);
    bool Stt=true; int ANS=0;
    int t; cin >> t; while(t--){
        cnt=len=in=0; 
        if(t==0){
            n=20000;
            forinc(i,0,n-1) {
                a[i]=i%2; if(a[i]==0) in++;
            }
        }
        else{
            n=d(gen);
            a[0]=0; in=1;
            forinc(i,1,n-1){
                a[i]=distrib(gen); if(a[i]==0) in++;
            }
        }
        
        //forinc(i,0,n-1) cout << a[i] << " "; cout << nn;
        Stt=(Stt and (count_mushrooms(n)==in));
        ANS=max(ANS,cnt);
        if(!Stt) cout << "wa3" << nn;
        //cout << (count_mushrooms(n)==in) << endl;
        //cout << count_mushrooms(n) << " " << in;
    }
    cout << ANS << nn << Stt; 
    
    
    int n; cin >> n; in=0; forinc(i,0,n-1){
        cin >> a[i]; if(a[i]==0) in++;
    }
    cout << count_mushrooms(n) << " " << in;
    
}
*/

Compilation message (stderr)

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:66:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |                 } if(A.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:68:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |                 } if(B.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:84:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   84 |                 } if(A.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:86:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   86 |                 } if(B.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:55:9: warning: 'stt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   55 |         if(stt){
      |         ^~

• Subtask 1: 92.623 / 100