| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 675582 | benjaminkleyn | 곤돌라 (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;
typedef long long ll;
unordered_map<int,int> cnt;
int valid(int n, int inputSeq[])
{
cnt.clear();
for (int i = 0; i < n; i++)
{
cnt[inputSeq[i]]++;
if (cnt[inputSeq[i]] > 1)
return 0;
}
int startPos = -1;
for (int i = 0; i < n; i++)
if (inputSeq[i] <= n)
{
startPos = (i - inputSeq[i] + 1 + n) % n;
break;
}
if (startPos == -1)
return 1;
for (int i = 0; i < n; i++)
if (inputSeq[i] <= n && startPos != (i - inputSeq[i] + 1 + n) % n)
return 0;
return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
vector<pair<int,int>> r;
int startPos = 0;
for (int i = 0; i < n; i++)
if (gondolaSeq[i] > n)
r.push_back({gondolaSeq[i], i});
else
startPos = (i - gondolaSeq[i] + 1 + n) % n;
sort(r.begin(), r.end());
int l = 0;
int cur_mx = n;
for (auto [newval, idx] : r)
{
int oldval = 1 + (idx - startPos + n) % n;
while (oldval != newval)
{
replacementSeq[l++] = oldval;
oldval = ++cur_mx;
}
}
return l;
}
const ll mod = 1000000009;
int countReplacement(int n, int inputSeq[])
{
if (!valid(n, inputSeq))
return 0;
vector<pair<int,int>> r;
int startPos = -1;
for (int i = 0; i < n; i++)
if (gondolaSeq[i] > n)
r.push_back({gondolaSeq[i], i});
else
startPos = (i - gondolaSeq[i] + 1 + n) % n;
if (startPos == -1)
return 0; // for now this is too complicated
sort(r.begin(), r.end());
ll res = 1;
int cur_mx = n;
for (auto [newval, idx] : r)
{
int oldval = 1 + (idx - startPos + n) % n;
// basically, seq[i] = ++cur_mx for some i until cur_mx = newval - 1.
// and then seq[idx] = ++cur_mx.
//
// the first one happens (newval - 1) - cur_mx times
// and the last one is fixed.
}
return res;
}