제출 #1146232

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1146232		enzy	곤돌라 (IOI14_gondola)	C++20	컴파일 에러	0 ms	0 KiB

gondola

//#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;
}
               

컴파일 시 표준 에러 (stderr) 메시지

/usr/bin/ld: /tmp/ccNVKzdZ.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccUNO4mH.o:gondola.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccNVKzdZ.o: in function `main':
grader.cpp:(.text.startup+0xae): undefined reference to `valid'
/usr/bin/ld: grader.cpp:(.text.startup+0x108): undefined reference to `countReplacement'
/usr/bin/ld: grader.cpp:(.text.startup+0x135): undefined reference to `replacement'
collect2: error: ld returned 1 exit status