Submission #1146230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146230		enzy	Gondola (IOI14_gondola)	C++20	60 / 100	27 ms	5888 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
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;
        }
    }
    int mut=1;
    if(ini==-1){
        for(int i=1;i<=n;i++){
            pos[i-1]=i;
            onde[i]=i-1;
        }
        mut=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;
    }
    int resp=1;
    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*=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;
        }
    }
    return resp*mut;
}

               

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