Submission #899616

# Submission time Handle Problem Language Result Execution time Memory
899616 2024-01-06T14:49:43 Z hihihahaa Counting Mushrooms (IOI20_mushrooms) C++17
92.623 / 100
6 ms 728 KB
#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

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){
      |         ^~
# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 452 KB Output is correct
7 Correct 4 ms 728 KB Output is correct
8 Correct 4 ms 468 KB Output is correct
9 Correct 4 ms 476 KB Output is correct
10 Correct 4 ms 624 KB Output is correct
11 Partially correct 5 ms 468 KB Output is partially correct
12 Correct 5 ms 468 KB Output is correct
13 Correct 4 ms 472 KB Output is correct
14 Correct 3 ms 468 KB Output is correct
15 Partially correct 5 ms 472 KB Output is partially correct
16 Partially correct 4 ms 468 KB Output is partially correct
17 Correct 3 ms 480 KB Output is correct
18 Correct 4 ms 468 KB Output is correct
19 Partially correct 4 ms 476 KB Output is partially correct
20 Correct 4 ms 624 KB Output is correct
21 Correct 4 ms 476 KB Output is correct
22 Partially correct 4 ms 468 KB Output is partially correct
23 Correct 4 ms 476 KB Output is correct
24 Correct 2 ms 464 KB Output is correct
25 Partially correct 4 ms 468 KB Output is partially correct
26 Partially correct 4 ms 476 KB Output is partially correct
27 Correct 4 ms 480 KB Output is correct
28 Partially correct 5 ms 464 KB Output is partially correct
29 Partially correct 4 ms 476 KB Output is partially correct
30 Partially correct 5 ms 472 KB Output is partially correct
31 Partially correct 4 ms 716 KB Output is partially correct
32 Partially correct 5 ms 468 KB Output is partially correct
33 Partially correct 4 ms 472 KB Output is partially correct
34 Partially correct 5 ms 476 KB Output is partially correct
35 Partially correct 4 ms 472 KB Output is partially correct
36 Partially correct 5 ms 704 KB Output is partially correct
37 Partially correct 4 ms 472 KB Output is partially correct
38 Partially correct 4 ms 472 KB Output is partially correct
39 Partially correct 4 ms 472 KB Output is partially correct
40 Partially correct 4 ms 476 KB Output is partially correct
41 Partially correct 4 ms 480 KB Output is partially correct
42 Partially correct 5 ms 472 KB Output is partially correct
43 Partially correct 4 ms 472 KB Output is partially correct
44 Partially correct 5 ms 472 KB Output is partially correct
45 Partially correct 4 ms 468 KB Output is partially correct
46 Partially correct 4 ms 700 KB Output is partially correct
47 Partially correct 4 ms 476 KB Output is partially correct
48 Partially correct 4 ms 468 KB Output is partially correct
49 Partially correct 4 ms 468 KB Output is partially correct
50 Partially correct 6 ms 704 KB Output is partially correct
51 Partially correct 4 ms 476 KB Output is partially correct
52 Partially correct 4 ms 472 KB Output is partially correct
53 Partially correct 4 ms 624 KB Output is partially correct
54 Partially correct 4 ms 468 KB Output is partially correct
55 Partially correct 4 ms 472 KB Output is partially correct
56 Partially correct 4 ms 476 KB Output is partially correct
57 Partially correct 4 ms 468 KB Output is partially correct
58 Partially correct 4 ms 468 KB Output is partially correct
59 Partially correct 4 ms 472 KB Output is partially correct
60 Partially correct 4 ms 472 KB Output is partially correct
61 Partially correct 4 ms 472 KB Output is partially correct
62 Correct 0 ms 344 KB Output is correct
63 Correct 0 ms 344 KB Output is correct
64 Correct 0 ms 344 KB Output is correct
65 Correct 0 ms 344 KB Output is correct
66 Correct 0 ms 344 KB Output is correct
67 Correct 0 ms 344 KB Output is correct
68 Correct 0 ms 344 KB Output is correct
69 Correct 0 ms 344 KB Output is correct
70 Correct 0 ms 344 KB Output is correct
71 Correct 1 ms 344 KB Output is correct
72 Correct 1 ms 344 KB Output is correct
73 Correct 0 ms 344 KB Output is correct
74 Correct 0 ms 344 KB Output is correct
75 Correct 0 ms 344 KB Output is correct
76 Correct 0 ms 344 KB Output is correct
77 Correct 0 ms 344 KB Output is correct
78 Correct 1 ms 344 KB Output is correct
79 Correct 1 ms 596 KB Output is correct
80 Correct 0 ms 344 KB Output is correct
81 Correct 0 ms 348 KB Output is correct
82 Correct 0 ms 344 KB Output is correct
83 Correct 0 ms 344 KB Output is correct
84 Correct 0 ms 344 KB Output is correct
85 Correct 1 ms 344 KB Output is correct
86 Correct 0 ms 344 KB Output is correct
87 Correct 1 ms 348 KB Output is correct
88 Correct 0 ms 344 KB Output is correct
89 Correct 1 ms 352 KB Output is correct
90 Correct 0 ms 344 KB Output is correct
91 Correct 0 ms 344 KB Output is correct