답안 #899616

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899616	2024-01-06T14:49:43 Z	hihihahaa	버섯 세기 (IOI20_mushrooms)	C++17	92.623 / 100	6 ms	728 KB

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

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.0

#	결과	실행 시간	메모리	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