| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1146261 | enzy | 곤돌라 (IOI14_gondola) | C++20 | 0 ms | 0 KiB |
//#include "gondola.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+7;
int marc[maxn], pos[maxn], onde[maxn], need[maxn];
int valid(int n, int v[])
{
int val, ini=-1, maior=1;
for(int i=0;i<n;i++) maior=max(maior,v[i]);
for(int i=1;i<=maior;i++) marc[maior]=0;
for(int i=0;i<n;i++){
if(marc[v[i]]) return 0;
marc[v[i]]++;
if(v[i]<=n){
val=v[i];
ini=i;
break;
}
}
if(ini==-1) return 1;
for(int i=ini+1;i<n;i++){
if(marc[v[i]]) return 0;
marc[v[i]]++;
val++; val%=(n+1);
if(!val) val++;
if(v[i]>n) continue;
if(val!=v[i]) return 0;
}
return 1;
}
int replacement(int n, int v[], int resp[])
{
int maior=1;
for(int i=0;i<n;i++) maior=max(maior,v[i]);
for(int i=1;i<=maior;i++) need[i]=pos[i]=marc[i]=0;
int val, ini=-1;
for(int i=0;i<n;i++){
if(v[i]<=n){
val=v[i];
ini=i;
break;
}
}
if(ini==-1){
for(int i=1;i<=n;i++){
pos[i-1]=i;
onde[i]=i-1;
}
}else{
int og=val;
for(int i=ini;i<n;i++){
pos[i]=val;
onde[val]=i;
val++; val%=(n+1);
if(!val) val++;
}
val=og;
for(int i=ini;i>=0;i--){
pos[i]=val;
onde[val]=i;
val--;
if(!val) val+=n;
}
}
for(int i=0;i<n;i++){
marc[v[i]]++;
need[v[i]]=i;
}
int id=0;
set<pair<int,int>>tira; // cara e onde ele tá
for(int i=1;i<=n;i++) if(!marc[i]) tira.insert({i,onde[i]});
for(int i=n+1;i<=maior;i++){
if(!marc[i]){ // posso colocar em qlqr lugar
auto f=tira.begin();
resp[id]=f->first;
int lugar=f->second;
onde[i]=lugar;
pos[lugar]=i;
tira.erase(f);
id++;
tira.insert({i,onde[i]});
}else{ // tenho q colocar no lugar certo
int at=pos[need[i]];
tira.erase({at,onde[at]});
pos[need[i]]=i;
resp[id]=at;
id++;
}
}
return id;
}
ll pot(ll x, ll y){
if(y==0) return 1;
if(y==1) return x;
ll at=pot(x,y/2); at%=mod;
at*=at; at%=mod;
at*=pot(x,y%2); at%=mod;
return at;
}
int countReplacement(int n, int v[])
{
if(!valid(n,v)) return 0;
int maior=1;
int ini=-1;
for(int i=0;i<n;i++){
if(v[i]<=n) ini=i;
}
ll resp=1;
vector<ll>process;
for(int i=0;i<n;i++) if(v[i]>n) process.push_back(v[i]);
sort(process.begin(),process.end());
ll a=process.size(), last=n;
for(ll b : process){
resp*=pot(a,b-last-1); resp%=mod;
last=b; a--;
}
int ret=resp;
if(ini==-1) ret=max(ret,n);
return ret;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int aux[]={6,5};
cout << countReplacement(2,aux) << endl;
}