| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 232073 | anonymous | 곤돌라 (IOI14_gondola) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "gondola.h"
#include <vector>
#include <iostream>
#define MAXN 100005
#define MAXV 250005
using namespace std;
int valid(int n, int Seq[])
{
bool has[MAXV]={}, b = false;
int pos, v;
for (int i=0; i<n; i++) {
if (Seq[i] <= n) {
pos = i;
v = Seq[i];
}
if (has[Seq[i]]) {return(0);}
has[Seq[i]]=true;
}
for (int i=0; i<n; i++) {
if (Seq[pos] > n) {}
else if (Seq[pos] != v) {return(0);}
pos = (pos+1) %n;
v= v == n ? 1 : v+1;
}
return(1);
}
//----------------------
int replacement(int n, int Seq[], int ans[])
{
int mx = 0, first=0, pos[MAXV]={}, Cur[MAXN];
bool b = false;
for (int i=0; i<n; i++) {
if (Seq[i] > n) {
pos[Seq[i]] = i+1;
if (!first) {first = i+1;}
} else if (!b) {
int p = i+1, v = Seq[i];
for (int j=0; j<n; j++) {
Cur[p] = v;
p = p == n ? 1: p+1;
v = v == n ? 1: v+1;
}
b=true;
}
mx = max(mx, Seq[i]);
}
if (!b) {
for (int i=1; i<=n; i++) {Cur[i] = i;}
}
for (int i=n+1; i<=mx; i++) {
if (pos[i] == 0) {
ans[i - n - 1] = Cur[first];
Cur[first] = i;
} else {
ans[i - n - 1] = Cur[pos[i]];
Cur[pos[i]] = i;
while (Cur[first] == Seq[first-1]) {first++;}
}
}
return(mx - n);
}