| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 908149 | tosivanmak | 곤돌라 (IOI14_gondola) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll negmod(ll num, ll n){
return ((num%n)+n)%n;
}
ll n,arr[100005];
bool ck(){
ll cnt=0;
map<ll,ll>mp;
for(int i=1;i<=n;i++){
if(arr[i]>n){
cnt++;
}
mp[arr[i]]++;
if(mp[arr[i]]>=2){
return 0;
}
}
if(cnt==n){
return 1;
}
ll first;
for(int i=1;i<=n;i++){
if(arr[i]<=n){
first=i;
break;
}
}
ll con[n+5];
ll need=arr[first];
for(int i=1;i<=n;i++){
ll lol= negmod(i-first+need,n);
if(!lol){lol=n;}
con[i]=lol;
}
bool ok=true;
for(int i=1;i<=n;i++){
if(arr[i]<=n&&arr[i]!=con[i]){
ok=0;
}
}
if(ok){
return 1;
}
else{
return 0;
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll subtask;
cin>>subtask;
if(subtask<=3){
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
if(ck()){
cout<<"1\n";
}
else{
cout<<"0\n";
}
}
else if(subtask<=6){
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i];
}
set<pair<ll,ll> >st;
ll recon[n+5];
ll cnt=0;
for(int i=1;i<=n;i++){
cnt+=(arr[i]>n);
}
if(cnt==n){
for(int i=1;i<=n;i++){
recon[i]=i;
}
}
else{
ll saga;
for(int i=1;i<=n;i++){
if(arr[i]<=n){
saga=i;
break;
}
}
ll need=arr[saga];
for(int i=1;i<=n;i++){
ll lol= negmod(i-saga+need,n);
if(!lol)lol=n;
recon[i]=lol;
}
}
for(int i=1;i<=n;i++){
st.insert({arr[i],i});
}
st.insert({300000,1});
ll last=n;
vector<ll>seq;
while(1){
pair<ll,ll>bruh=*st.lower_bound({last+1,0});
if(bruh.first==300000){
break;
}
seq.push_back(recon[bruh.second]);
for(int i=last+2;i<=bruh.first;i++){
seq.push_back(i-1);
}
last=bruh.first;
}
cout<<seq.size()<<'\n';
for(auto& u: seq){
cout<<u<<"\n";
}
}
}