oj.uz

답안 #773746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
773746 2023-07-05T08:06:48 Z ono_de206 버섯 세기 (IOI20_mushrooms) C++14
100 / 100
 7 ms 396 KB 
#include "mushrooms.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// #define int long long
 
typedef long long ll;
typedef vector<int> vi;
typedef set<int> si;
typedef multiset<int> msi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;

const int bl = 200;

int solveSmall(int n) {
	int ret = 0;
	for(int i = 1; i < n; i += 2) {
		vector<int> ask;
		ask.pb(i);
		ask.pb(0);
		if(i + 1 < n) ask.pb(i + 1);
		ret += use_machine(ask);
	}
	return n - ret;
}

int count_mushrooms(int n) {
	if(n / 2 <= 226) return solveSmall(n);
	vector<int> a{0}, b;
	int did = 0;

	auto check = [&]() -> void {
		if(b.size() > a.size()) {
			swap(a, b);
			did ^= 1;
		}
	};

	queue<int> m;
	for(int i = 5; i < n; i++) {
		m.push(i);
	}

	if(use_machine(vector<int>{0, 1})) b.pb(1);
	else a.pb(1); 
	if(use_machine(vector<int>{0, 2})) b.pb(2);
	else a.pb(2);
	check();

	int tmp = use_machine(vector<int>{a[0], 3, a[1], 4});
	if(tmp & 1) b.pb(4);
	else a.pb(4);
	if(tmp > 1) b.pb(3);
	else a.pb(3); 
	check();

	while(a.size() + b.size() < bl) {
		vector<int> v;
		for(int i = 0; i < 3; i++) {
			v.pb(m.front()); m.pop();
		}
		int tmp = use_machine(vector<int>{a[0], v[0], a[1], v[1], a[2], v[2]});
		if(tmp == 2 || tmp == 3) {
			if(tmp == 2) a.pb(v[2]);
			else b.pb(v[2]);
			check();
			v.pop_back();

			if(b.size() >= 2) {
				for(int i = 0; i < 2; i++) {
					v.pb(m.front()); m.pop();
				}
				tmp = use_machine(vector<int>{b[0], v[0], b[1], a[0], v[1], a[1], v[2], a[2], v[3]}) - 1;
				if(tmp >= 4) {
					a.pb(v[0]);
					b.pb(v[1]);
					tmp -= 4;
				} else {
					a.pb(v[1]);
					b.pb(v[0]);
				}

				if(tmp & 1) b.pb(v[3]);
				else a.pb(v[3]);

				if(tmp > 1) b.pb(v[2]);
				else a.pb(v[2]);
			} else {
				if(use_machine(vector<int>{a[0], v[0]})) {
					b.pb(v[0]);
					a.pb(v[1]);
				} else {
					a.pb(v[0]);
					b.pb(v[1]);
				}
			}
		} else {
			if(tmp == 0) {
				a.insert(a.end(), all(v));
			} else if(tmp == 1) {
				a.pb(v[0]); a.pb(v[1]);
				b.pb(v[2]);
			} else if(tmp == 4) {
				a.pb(v[2]);
				b.pb(v[0]); b.pb(v[1]);
			} else {
				b.insert(b.end(), all(v));
			}
		}
		check();
	}
	vector<int> ask;
	int A = a.size(), B = b.size(), id = 0;
	while(m.size()) {
		int now = m.front(); m.pop();
		ask.pb(a[id]);
		ask.pb(now);
		id++;
		if(id == a.size()) {
			int tmp = use_machine(ask);
			A += id - (tmp + 1) / 2;
			B += (tmp + 1) / 2;
			if(tmp % 2 == 0) a.pb(ask.back());
			else b.pb(ask.back());
			id = 0;
			if(a.size() < b.size()) {
				swap(A, B);
				check();
			}
			ask.clear();
		}
	}
	if(ask.size()) {
		int tmp = use_machine(ask);
		A += id - (tmp + 1) / 2;
		B += (tmp + 1) / 2;
	}
	if(did) swap(A, B);	
	return A;
}

Compilation message

mushrooms.cpp: In function 'int count_mushrooms(int)':
mushrooms.cpp:127:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |   if(id == a.size()) {
      |      ~~~^~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 4 ms 336 KB Output is correct
8 Correct 5 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 5 ms 392 KB Output is correct
11 Correct 6 ms 336 KB Output is correct
12 Correct 5 ms 336 KB Output is correct
13 Correct 4 ms 336 KB Output is correct
14 Correct 3 ms 348 KB Output is correct
15 Correct 6 ms 396 KB Output is correct
16 Correct 6 ms 336 KB Output is correct
17 Correct 3 ms 348 KB Output is correct
18 Correct 5 ms 336 KB Output is correct
19 Correct 4 ms 396 KB Output is correct
20 Correct 5 ms 336 KB Output is correct
21 Correct 5 ms 336 KB Output is correct
22 Correct 5 ms 336 KB Output is correct
23 Correct 6 ms 368 KB Output is correct
24 Correct 3 ms 336 KB Output is correct
25 Correct 6 ms 392 KB Output is correct
26 Correct 5 ms 396 KB Output is correct
27 Correct 6 ms 336 KB Output is correct
28 Correct 7 ms 336 KB Output is correct
29 Correct 7 ms 336 KB Output is correct
30 Correct 7 ms 336 KB Output is correct
31 Correct 5 ms 336 KB Output is correct
32 Correct 5 ms 336 KB Output is correct
33 Correct 6 ms 336 KB Output is correct
34 Correct 5 ms 336 KB Output is correct
35 Correct 5 ms 396 KB Output is correct
36 Correct 7 ms 392 KB Output is correct
37 Correct 6 ms 336 KB Output is correct
38 Correct 5 ms 336 KB Output is correct
39 Correct 6 ms 396 KB Output is correct
40 Correct 6 ms 336 KB Output is correct
41 Correct 5 ms 336 KB Output is correct
42 Correct 7 ms 336 KB Output is correct
43 Correct 4 ms 392 KB Output is correct
44 Correct 7 ms 396 KB Output is correct
45 Correct 6 ms 336 KB Output is correct
46 Correct 5 ms 396 KB Output is correct
47 Correct 5 ms 336 KB Output is correct
48 Correct 7 ms 336 KB Output is correct
49 Correct 7 ms 396 KB Output is correct
50 Correct 5 ms 336 KB Output is correct
51 Correct 6 ms 336 KB Output is correct
52 Correct 6 ms 392 KB Output is correct
53 Correct 5 ms 336 KB Output is correct
54 Correct 6 ms 336 KB Output is correct
55 Correct 6 ms 336 KB Output is correct
56 Correct 5 ms 336 KB Output is correct
57 Correct 6 ms 344 KB Output is correct
58 Correct 5 ms 336 KB Output is correct
59 Correct 6 ms 396 KB Output is correct
60 Correct 4 ms 392 KB Output is correct
61 Correct 5 ms 336 KB Output is correct
62 Correct 1 ms 208 KB Output is correct
63 Correct 0 ms 208 KB Output is correct
64 Correct 0 ms 208 KB Output is correct
65 Correct 1 ms 208 KB Output is correct
66 Correct 0 ms 208 KB Output is correct
67 Correct 0 ms 208 KB Output is correct
68 Correct 0 ms 208 KB Output is correct
69 Correct 0 ms 208 KB Output is correct
70 Correct 0 ms 208 KB Output is correct
71 Correct 0 ms 208 KB Output is correct
72 Correct 0 ms 208 KB Output is correct
73 Correct 1 ms 208 KB Output is correct
74 Correct 0 ms 208 KB Output is correct
75 Correct 1 ms 208 KB Output is correct
76 Correct 0 ms 208 KB Output is correct
77 Correct 0 ms 208 KB Output is correct
78 Correct 0 ms 208 KB Output is correct
79 Correct 0 ms 208 KB Output is correct
80 Correct 0 ms 208 KB Output is correct
81 Correct 1 ms 208 KB Output is correct
82 Correct 0 ms 208 KB Output is correct
83 Correct 0 ms 208 KB Output is correct
84 Correct 0 ms 208 KB Output is correct
85 Correct 0 ms 208 KB Output is correct
86 Correct 0 ms 208 KB Output is correct
87 Correct 1 ms 208 KB Output is correct
88 Correct 0 ms 208 KB Output is correct
89 Correct 0 ms 208 KB Output is correct
90 Correct 1 ms 208 KB Output is correct
91 Correct 0 ms 208 KB Output is correct