| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 314795 | nonthaphat | 버섯 세기 (IOI20_mushrooms) | C++14 | 12 ms | 388 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef pair<pii, int> piipi;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;
typedef pair<ll, pii> plpii;
typedef pair<db, db> pdd;
typedef pair<ld, ld> pldd;
typedef vector<int> vi;
typedef vector<pii> vii;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FOR2(i, a, b) for(int i=(a);i<=(b);++i)
#define ROF(i, a, b) for(int i=(b)-1;i>=(a);--i)
#define ROF2(i, a, b) for(int i=(b);i>=(a);--i)
#define GO(i, x) for(auto &i : x)
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define eb emplace_back
#define pf push_front
#define pb push_back
#define lb lower_bound
#define up upper_bound
template<typename T> inline bool min2(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool max2(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
const int mod = 1e9 + 7;
// const int mod = 998244353;
const int P1 = 999983, P2 = 999979;
const ld PI = acos((ld)-1);
const int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
const ll INF = 1e18;
const int N = 1e6;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int M = 90;
int use_machine(vector<int> x);
void partV1(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
while(count_A < 2 && count_B < 2){
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++;
}
}
void partV2(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
while((count_A < 3 || count_B < 2) && (count_A < 2 || count_B < 3) && count_A < M && count_B < M){
bool sw = 0;
if(count_A < count_B){
sw = 1;
swap(A, B);
swap(count_A, count_B);
}
vector<int> x;
x.push_back(i);
x.push_back(A[0]);
x.push_back(i+1);
x.push_back(A[1]);
int result = use_machine(x);
switch(result){
case 0:
A.push_back(i);
A.push_back(i+1);
count_A += 2;
break;
case 1:
B.push_back(i);
A.push_back(i+1);
count_A++;
count_B++;
break;
case 2:
A.push_back(i);
B.push_back(i+1);
count_A++;
count_B++;
break;
default:
B.push_back(i);
B.push_back(i+1);
count_B += 2;
}
if(sw){
swap(A, B);
swap(count_A, count_B);
}
i += 2;
}
}
void partV3(int &i, vector<int> &A, vector<int> &B, int &count_A, int &count_B){
while(count_A < M && count_B < M){
bool sw = 0;
if(count_A < count_B){
sw = 1;
swap(A, B);
swap(count_A, count_B);
}
vector<int> x;
x.push_back(i);
x.push_back(A[0]);
x.push_back(i+1);
x.push_back(A[1]);
x.push_back(i+2);
x.push_back(A[2]);
int result = use_machine(x);
if(result%2 == 0){
A.push_back(i);
count_A++;
}
else{
B.push_back(i);
count_B++;
}
if(result-result%2 == 0){
A.push_back(i+1);
A.push_back(i+2);
count_A += 2;
i += 3;
}
else if(result-result%2 == 4){
B.push_back(i+1);
B.push_back(i+2);
count_B += 2;
i += 3;
}
else{
vector<int> x;
x.push_back(B[0]);
x.push_back(i+1);
x.push_back(B[1]);
x.push_back(A[0]);
x.push_back(i+2);
x.push_back(A[1]);
x.push_back(i+3);
x.push_back(A[2]);
x.push_back(i+4);
int result = use_machine(x);
switch(result){
case 1:
B.push_back(i+1);
A.push_back(i+2);
A.push_back(i+3);
A.push_back(i+4);
count_A += 3;
count_B += 1;
break;
case 2:
B.push_back(i+1);
A.push_back(i+2);
A.push_back(i+3);
B.push_back(i+4);
count_A += 2;
count_B += 2;
break;
case 3:
B.push_back(i+1);
A.push_back(i+2);
B.push_back(i+3);
A.push_back(i+4);
count_A += 2;
count_B += 2;
break;
case 4:
B.push_back(i+1);
A.push_back(i+2);
B.push_back(i+3);
B.push_back(i+4);
count_A += 1;
count_B += 3;
break;
case 5:
A.push_back(i+1);
B.push_back(i+2);
A.push_back(i+3);
A.push_back(i+4);
count_A += 3;
count_B += 1;
break;
case 6:
A.push_back(i+1);
B.push_back(i+2);
A.push_back(i+3);
B.push_back(i+4);
count_A += 2;
count_B += 2;
break;
case 7:
A.push_back(i+1);
B.push_back(i+2);
B.push_back(i+3);
A.push_back(i+4);
count_A += 2;
count_B += 2;
break;
default:
A.push_back(i+1);
B.push_back(i+2);
B.push_back(i+3);
B.push_back(i+4);
count_A += 1;
count_B += 3;
}
i += 5;
}
if(sw){
swap(A, B);
swap(count_A, count_B);
}
}
}
int count_mushrooms(int n){
int count_A = 1, count_B = 0;
int i = 1;
vector<int> A, B;
A.push_back(0);
if(n <= 226){
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;
}
partV1(i, A, B, count_A, count_B);
partV2(i, A, B, count_A, count_B);
partV3(i, A, B, count_A, count_B);
while(i < n){
bool sw = 0;
if(A.size() < B.size()){
sw = 1;
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);
if(result%2 == 0){
A.push_back(i);
count_A++;
}
else{
B.push_back(i);
count_B++;
}
count_B += result/2;
count_A += (L-1) - result/2;
if(sw){
swap(A, B);
swap(count_A, count_B);
}
i += L;
}
return count_A;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||