제출 #1146216

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146216		enzy	Gondola (IOI14_gondola)	C++20	10 / 100	5 ms	584 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;

int valid(int n, int v[])
{
    int val, ini;
    for(int i=0;i<n;i++){
        if(v[i]<=n){
            val=v[i];
            ini=i;
            break;
        }
    }
    for(int i=ini+1;i<n;i++){
        val++; val%=(n+1);
        if(!val) val++;
        if(v[i]>n) continue;
        if(val!=v[i]) return 0;
    }
    return 1;
}

int marc[maxn], pos[maxn], onde[maxn], need[maxn];
int replacement(int n, int v[], int resp[])
{
    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=og;
        for(int i=ini;i>=0;i--){
            pos[i]=val;
            onde[val]=i;
            val--;
        }
    }
    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;
    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 inputSeq[])
{
    return -3;
}
               

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 20
• Subtask 7: 0 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10