답안 #1055169

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1055169	2024-08-12T15:02:55 Z	pcc	버섯 세기 (IOI20_mushrooms)	C++17	74.0984 / 100	6 ms	600 KB

mushrooms

#include "mushrooms.h"
#include <bits/stdc++.h>
using namespace std;

const int B = 125;
//const int B = 3;

vector<int> perm;

int ask(vector<int> v){
	//for(auto &i:v)i = perm[i];
	return use_machine(v);
}

int count_mushrooms(int n) {
	if(n<=B*2){
		int ans = 1;
		for(int i = 1;i<n;i++){
			int re = use_machine(vector<int>({0,i}));
			if(!re)ans++;
		}
		return ans;
	}
	srand(time(NULL));
	for(int i = 0;i<n;i++)perm.push_back(i);
	random_shuffle(perm.begin()+1,perm.end());
	vector<int> v[2];
	v[0].push_back(0);
	int nxt = 1;
	for(int i = 1;max(v[0].size(),v[1].size())<B;i++){
		int re = ask(vector<int>({0,i*3-2,i*3-1,i*3}));
		if(re == 0){
			v[0].push_back(i*3-2);
			v[0].push_back(i*3-1);
			v[0].push_back(i*3);
		}
		else if(re == 3){
			v[1].push_back(i*3-2);
			v[0].push_back(i*3-1);
			v[1].push_back(i*3);
		}
		else if(re == 1){
			v[1].push_back(i*3);
			re = ask(vector<int>({0,i*3,i*3-2,i*3-1}));
			if(re == 1){
				v[1].push_back(i*3-2);
				v[1].push_back(i*3-1);
			}
			else if(re == 2){
				v[0].push_back(i*3-2);
				v[0].push_back(i*3-1);
			}
			else if(re == 3){
				v[0].push_back(i*3-2);
				v[1].push_back(i*3-1);
			}
			else assert(false);
		}
		else if(re == 2){
			v[0].push_back(i*3);
			int re = ask(vector<int>({i*3-2,0,i*3-1,i*3}));
			if(re == 2){
				v[0].push_back(i*3-2);
				v[1].push_back(i*3-1);
			}
			else if(re == 3){
				v[1].push_back(i*3-2);
				v[1].push_back(i*3-1);
			}
			else if(re == 1){
				v[1].push_back(i*3-2);
				v[0].push_back(i*3-1);
			}
			else assert(false);
		}
		nxt = i*3+1;
	}
	int dir = (v[0].size()<v[1].size());
	int cnt[2] = {v[0].size(),v[1].size()};
	/*
	cerr<<"DIR: "<<dir<<endl;for(auto &i:v[dir])cerr<<i<<',';cerr<<endl;
	cerr<<"NXT: "<<nxt<<endl;
	*/
	for(int i = nxt;i<n;i+=v[dir].size()){
		vector<int> vv;
		for(int j = i;j<min(n,i+(int)v[dir].size());j++)vv.push_back(j);
		//cerr<<"VV: ";for(auto &j:vv)cerr<<j<<',';cerr<<endl;
		vector<int> req;
		for(int j = 0;j<vv.size();j++){
			req.push_back(v[dir][j]);
			req.push_back(vv[j]);
		}
		//cerr<<nxt<<','<<vv.size()<<":"<<endl;for(auto &j:req)cerr<<j<<',';cerr<<endl;
		int re = ask(req);
		if(re&1)re++;
		re>>=1;
		cnt[dir^1] += re;
		cnt[dir] += vv.size()-re;
	}
	return cnt[0];
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:79:25: warning: narrowing conversion of 'v[0].std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   79 |  int cnt[2] = {v[0].size(),v[1].size()};
      |                ~~~~~~~~~^~
mushrooms.cpp:79:37: warning: narrowing conversion of 'v[1].std::vector<int>::size()' from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
   79 |  int cnt[2] = {v[0].size(),v[1].size()};
      |                            ~~~~~~~~~^~
mushrooms.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |   for(int j = 0;j<vv.size();j++){
      |                 ~^~~~~~~~~~

Subtask #1

74.0984 / 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	1 ms	344 KB	Output is correct
5	Correct	1 ms	344 KB	Output is correct
6	Correct	1 ms	344 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	3 ms	600 KB	Output is correct
9	Correct	3 ms	600 KB	Output is correct
10	Partially correct	3 ms	600 KB	Output is partially correct
11	Partially correct	3 ms	600 KB	Output is partially correct
12	Partially correct	3 ms	600 KB	Output is partially correct
13	Partially correct	3 ms	600 KB	Output is partially correct
14	Correct	2 ms	552 KB	Output is correct
15	Partially correct	4 ms	600 KB	Output is partially correct
16	Partially correct	3 ms	600 KB	Output is partially correct
17	Correct	2 ms	344 KB	Output is correct
18	Partially correct	3 ms	600 KB	Output is partially correct
19	Partially correct	4 ms	600 KB	Output is partially correct
20	Partially correct	5 ms	600 KB	Output is partially correct
21	Partially correct	4 ms	600 KB	Output is partially correct
22	Partially correct	5 ms	600 KB	Output is partially correct
23	Partially correct	5 ms	600 KB	Output is partially correct
24	Correct	2 ms	344 KB	Output is correct
25	Partially correct	3 ms	600 KB	Output is partially correct
26	Partially correct	4 ms	600 KB	Output is partially correct
27	Partially correct	4 ms	600 KB	Output is partially correct
28	Partially correct	6 ms	600 KB	Output is partially correct
29	Partially correct	3 ms	600 KB	Output is partially correct
30	Partially correct	4 ms	600 KB	Output is partially correct
31	Partially correct	3 ms	600 KB	Output is partially correct
32	Partially correct	6 ms	600 KB	Output is partially correct
33	Partially correct	3 ms	600 KB	Output is partially correct
34	Partially correct	3 ms	600 KB	Output is partially correct
35	Partially correct	3 ms	600 KB	Output is partially correct
36	Partially correct	5 ms	600 KB	Output is partially correct
37	Partially correct	5 ms	600 KB	Output is partially correct
38	Partially correct	3 ms	600 KB	Output is partially correct
39	Partially correct	4 ms	600 KB	Output is partially correct
40	Partially correct	3 ms	600 KB	Output is partially correct
41	Partially correct	5 ms	600 KB	Output is partially correct
42	Partially correct	4 ms	600 KB	Output is partially correct
43	Partially correct	3 ms	600 KB	Output is partially correct
44	Partially correct	5 ms	600 KB	Output is partially correct
45	Partially correct	4 ms	600 KB	Output is partially correct
46	Partially correct	5 ms	600 KB	Output is partially correct
47	Partially correct	6 ms	600 KB	Output is partially correct
48	Partially correct	5 ms	600 KB	Output is partially correct
49	Partially correct	3 ms	600 KB	Output is partially correct
50	Partially correct	5 ms	600 KB	Output is partially correct
51	Partially correct	5 ms	600 KB	Output is partially correct
52	Partially correct	3 ms	600 KB	Output is partially correct
53	Partially correct	5 ms	600 KB	Output is partially correct
54	Partially correct	4 ms	600 KB	Output is partially correct
55	Partially correct	3 ms	600 KB	Output is partially correct
56	Partially correct	5 ms	600 KB	Output is partially correct
57	Partially correct	5 ms	600 KB	Output is partially correct
58	Partially correct	3 ms	600 KB	Output is partially correct
59	Partially correct	4 ms	600 KB	Output is partially correct
60	Partially correct	3 ms	600 KB	Output is partially correct
61	Partially correct	3 ms	600 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	0 ms	344 KB	Output is correct
72	Correct	0 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	440 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	0 ms	344 KB	Output is correct
80	Correct	0 ms	344 KB	Output is correct
81	Correct	0 ms	344 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	0 ms	344 KB	Output is correct
86	Correct	0 ms	344 KB	Output is correct
87	Correct	0 ms	344 KB	Output is correct
88	Correct	0 ms	344 KB	Output is correct
89	Correct	0 ms	344 KB	Output is correct
90	Correct	0 ms	344 KB	Output is correct
91	Correct	0 ms	344 KB	Output is correct