Submission #899222

#	Time	Username	Problem	Language	Result	Execution time	Memory
899222		hihihahaa	Counting Mushrooms (IOI20_mushrooms)	C++17	0 / 100	0 ms	344 KiB

mushrooms

#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;
#define forinc(i,a,b) for(i=a;i<=b;i++)
#define fordec(i,a,b) for(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 i,in,res,debug;
int a[1000000];
/*
int use_machine(vector<int> x){
    int ans=0;
    forinc(i,1,debug-1){
        if(a[x[i]]!=a[x[i-1]]) ans++;
    } 
    return ans;
}
*/
int count_mushrooms(int n){
    bool stt; int cut=sqrt(n); 
    if(n<100) cut=1;
    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){
                    stt=1; pt+=2; break;
                } if(B.size()>=cut){
                    stt=0; pt+=2; break;
                }
            }
        }
    }
    //cout << pt << " " << 2 << nn;
    // step 3 
    int ans=A.size();
    if(stt){
        int k=A.size();
        while(pt<n){
            vector<int> out(2*min(k,n-pt),0); debug=2*min(k,n-pt); for(i=0; i<debug/2; i++){
                out[2*i]=A[i]; 
                out[2*i+1]=pt; 
                pt++;
            } 
            res=use_machine(out);
            ans+=i/2-(res+1)/2; 
        }
    }
    else{
        int k=B.size();
        while(pt<n){
            vector<int> out(2*min(k,n-pt),0); debug=2*min(k,n-pt); for(i=0; i<debug/2; i++){
                out[2*i]=B[i];
                out[2*i+1]=pt;
                pt++;
            } res=use_machine(out);
            ans+=(res+1)/2; 
        }
    }
    //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);
    int n; cin >> n;
    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;
    cout << in << " " << count_mushrooms(n));
    
    
    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:57:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |                 } if(A.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:59:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   59 |                 } if(B.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:75:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   75 |                 } if(A.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:77:30: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   77 |                 } if(B.size()>=cut){
      |                      ~~~~~~~~^~~~~
mushrooms.cpp:86:5: warning: 'stt' may be used uninitialized in this function [-Wmaybe-uninitialized]
   86 |     if(stt){
      |     ^~

• Subtask 1: 0 / 100