| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 138691 | Bohoty | Gondola (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#include "gondola.h"
// #include "grader.cpp"
using namespace std;
const int N = 100 + 5, mod = 1e9 + 7;
int a, b, c, m;
int dp[N][N][N];
long long solve(int x, int y, int z, bool start){
if (x > a || y > b || z > c)
return 0;
if (x == a && y == b && z == c)
return 1;
if (~dp[x][y][z])
return dp[x][y][z];
int n_x, n_y, n_z;
if (start)
n_x = n_y = n_z;
else
n_x = n_y = n_z = max(max(x, y), z);
return dp[x][y][z] = (solve(x + 1, y, z, 0)
+ solve(x, y + 1, z, 0)
+ solve(x, y, z + 1, 0)) % mod;
}
int valid(int n, int inputSeq[]){
int mn = 1e9;
int idx = -1;
map < int, int > mp;
for(int i = 0 ; i < n ; i++){
mp[inputSeq[i]]++;
if (inputSeq[i] < mn){
mn = inputSeq[i], idx = i;
}
}
for(auto it :mp){
if (it.second > 1)
return 0;
}
int intended = mn;
if (intended > n)
return 1;
for(int i = 0 ; i < n ; i++){
int cur = inputSeq[(i + idx) % n];
if (cur != intended){
if (cur <= n)
return 0;
}
intended++;
if (intended > n)
intended -= n;
}
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
int mn = 1e9;
int idx = -1;
set < int > st, elements;
int f[250001], now[250001];
memset(f,0,sizeof f);
memset(now,0,sizeof now);
for(int i = 0 ; i < 250001 ; i++)
now[i] = i;
for(int i = n + 1 ; i <= 250000 ; i++)
st.insert(i);
for(int i = 0 ; i < n ; i++){
if (gondolaSeq[i] < mn){
mn = gondolaSeq[i], idx = i;
}
}
int intended = mn;
if (intended > n)
intended = 1;
for(int i = 0 ; i < n ; i++){
int cur = gondolaSeq[(i + idx) % n];
if (cur != intended){
mp[intended] = cur;
f[cur] = intended;
elements.insert(intended);
}
intended++;
if (intended > n)
intended -= n;
}
int j = 0;
for(int it = n + 1 ; it <= 300000 ; it++)
if (elements.empty())
break;
if (f[it]){
int z = f[it];
replacementSeq[j++] = now[z];
elements.erase(f[it]);
}
else {
int z = *elements.begin();
replacementSeq[j++] = now[z];
now[z] = it;
}
}
return j;
}
int countReplacement(int n, int inputSeq[]){
a= b= c= m = 0;
memset(dp, -1, sizeof dp);
int mn = 1e9;
int idx = -1;
for(int i = 0 ; i < n ; i++){
if (inputSeq[i] < mn){
mn = inputSeq[i], idx = i;
}
}
int intended = mn;
vector < pair < int, int > > v;
for(int i = 0 ; i < n ; i++){
int cur = inputSeq[(i + idx) % n];
if (cur != intended){
v.push_back({cur, intended});
}
intended++;
if (intended > n)
intended -= n;
}
m = n;
int x, y, z;
x = y = z = 0;
if (v.size()){
x = v[0].second;
a = v[0].first;
}
if (v.size() > 1){
y = v[1].second;
b = v[1].first;
}
if (v.size() > 2){
z = v[2].second;
c = v[2].first;
}
return solve(x, y, z, 1);
}