| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1146232 | 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=3e5+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;
}
int countReplacement(int n, int v[])
{
if(!valid(n,v)) return 0;
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;
}
}
ll resp=1;
if(ini==-1){
for(int i=1;i<=n;i++){
pos[i-1]=i;
onde[i]=i-1;
}
resp=n;
}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;
}
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*=(ll)tira.size(); resp%=mod;
int lugar=f->second;
onde[i]=lugar;
pos[lugar]=i;
tira.erase(f);
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;
}
}
int ret=resp;
return ret;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int aux[]={3,4};
cout << countReplacement(2,aux) << endl;
}