제출 #314690

#제출 시각아이디문제언어결과실행 시간메모리
314690neizod버섯 세기 (IOI20_mushrooms)C++17
0 / 100
0 ms256 KiB
// WIP: REFACTORING #include "mushrooms.h" #include <bits/stdc++.h> using namespace std; const int M = 100; bool swapped; int count_A, count_B, i; vector<int> A, B; void handle_parity(int parity) { if (parity == 0) { A.push_back(i); } else { B.push_back(i); } i += 1; } void get_same_two_pivots() { while (A.size() < 2 and B.size() < 2) { handle_parity(use_machine({ 0, i })); } } void get_mixed_three_two_pivots() { // TODO refactor while condition --> can use do-until while ( (A.size() < 3 or B.size() < 2) and (A.size() < 2 or B.size() < 3) and (A.size() < M and B.size() < M) ) { if (A.size() < B.size()) { swapped = not swapped; swap(A, B); } int result = use_machine({ i, A[0], i+1, A[1] }); handle_parity(result%2); handle_parity(result/2); } } void get_same_many_pivots() { // TODO argument: limits // TODO M is somewhat magic number, can we determine them in term of n? while (A.size() < M && B.size() < M) { if (A.size() < B.size()) { swapped = not swapped; swap(A, B); } int result = use_machine({ i, A[0], i+1, A[1], i+2, A[2] }); int parity = result % 2; switch (parity) { case 0: A.push_back(i); break; case 1: B.push_back(i); break; } switch (result - parity) { case 0: A.insert(A.end(), { i+1, i+2 }); i += 3; break; case 4: B.insert(B.end(), { i+1, i+2 }); i += 3; break; case 2: switch (use_machine({ B[0], i+1, B[1], A[0], i+2, A[1], i+3, A[2], i+4 })) { case 1: A.insert(A.end(), { i+2, i+3, i+4 }); B.insert(B.end(), { i+1 }); break; case 2: A.insert(A.end(), { i+2, i+3 }); B.insert(B.end(), { i+1, i+4 }); break; case 3: A.insert(A.end(), { i+2, i+4 }); B.insert(B.end(), { i+1, i+3 }); break; case 4: A.insert(A.end(), { i+2 }); B.insert(B.end(), { i+1, i+3, i+4 }); break; case 5: A.insert(A.end(), { i+1, i+3, i+4 }); B.insert(B.end(), { i+2 }); break; case 6: A.insert(A.end(), { i+1, i+3 }); B.insert(B.end(), { i+2, i+4 }); break; case 7: A.insert(A.end(), { i+1, i+4 }); B.insert(B.end(), { i+2, i+3 }); break; default: // TODO XXX FIXME PLS NO DEFAULT!! A.insert(A.end(), { i+1 }); B.insert(B.end(), { i+2, i+3, i+4 }); } i += 5; } } } void count_the_rest(int n) { count_A = A.size(); count_B = B.size(); while (i < n) { bool swapped = false; if (A.size() < B.size()) { swapped = not swapped; swap(A, B); swap(count_A, count_B); } vector<int> x; int L = min((int)A.size(), n-i); for (int j=0; j<L; j++) { x.push_back(i+j); x.push_back(A[j]); } int result = use_machine(x); int parity = result % 2; if (parity == 0) { A.push_back(i); count_A += 1; } else { B.push_back(i); count_B += 1; } count_B += result/2; count_A += (L-1) - result/2; i += L; } if (swapped) { swapped = not swapped; swap(A, B); swap(count_A, count_B); } } int naive(int n) { while (i < n) { vector<int> x; x.push_back(0); x.push_back(i); int result = use_machine(x); if (result == 0 ) { A.push_back(i); count_A++; } else { B.push_back(i); count_B++; } i++; } return count_A; } int count_mushrooms(int n) { swapped = false; i = 1; A = { 0 }; B = { }; if (n <= 226) { return naive(n); } get_same_two_pivots(); get_mixed_three_two_pivots(); get_same_many_pivots(); count_the_rest(n); return count_A; }
#Verdict Execution timeMemoryGrader output
Fetching results...