| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 737586 | esomer | 곤돌라 (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
long long pw(int a, int b){
if(b == 0) return 1;
if(b % 2 == 0){
long long x = pw(a / 2, b);
return (x * x) % MOD;
}else{
long long x = pw(a / 2, b);
x = (x * x) % MOD;
return (x * a) % MOD;
}
}
int valid(int n, int* inputSeq){
vector<int> cnt(n+1, 0);
int mn = 1e9;
int ind;
for(int i = 0; i < n; i++){
if(mn > inputSeq[i]){
mn = inputSeq[i];
ind = i;
}
cnt[inputSeq[i]]++;
if(cnt[inputSeq[i]] > 1) return 0;
}
if(mn > n) return 1;
int lst = mn;
for(int i = ind + 1; i % n != ind; i++){
if(inputSeq[i % n] <= n){
if(lst > inputSeq[i % n]) return 0;
lst = inputSeq[i % n];
}
}
return 1;
}
int replacement(int n, int* gondolaSeq, int* replacementSeq){
int ind = 0;
int add = 1e9;
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
if(gondolaSeq[i] <= n && gondolaSeq[i] < add){
add = gondolaSeq[i];
ind = i;
}
if(gondolaSeq[i] > n){
v.push_back({gondolaSeq[i], i});
}
}
if(add == 1e9) add = 1;
sort(v.begin(), v.end());
int nxt = n + 1;
int curr = 0;
for(auto p : v){
int initial;
if(p.second < ind) initial = n - ind + p.second + add;
else initial = p.second - ind + add;
replacementSeq[curr] = initial; curr++;
while(nxt != p.first){
replacementSeq[curr] = nxt; nxt++; curr++;
}
nxt = p.first + 1;
}
return curr;
}
int countReplacement(int n, int* inputSeq){
vector<int> cnt(n+1, 0);
int mn = 1e9;
int mx = 0;
int ind;
int broken = 0;
vector<int> v;
for(int i = 0; i < n; i++){
if(mn > inputSeq[i]){
mn = inputSeq[i];
ind = i;
}
cnt[inputSeq[i]]++;
if(cnt[inputSeq[i]] > 1) return 0;
mx = max(mx, inputSeq[i]);
if(inputSeq[i] > n) {broken++; v.push_back(inputSeq[i]);}
}
int lst = mn;
for(int i = ind + 1; i % n != ind; i++){
if(inputSeq[i % n] <= n){
if(lst > inputSeq[i % n]) return 0;
lst = inputSeq[i % n];
}
}
long long ans = 1;
lst = n;
for(int x : v){
ans *= pw(broken, x - lst); ans %= MOD;
broken--; lst = x;
}
return (int)ans;
}
//~ int main(){
//~ }