Submission #396906

#	Time	Username	Problem	Language	Result	Execution time	Memory
396906		definitelynotmee	곤돌라 (IOI14_gondola)	C++98	75 / 100	42 ms	4496 KiB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INFL = (1LL<<62)-1;
const int INF = (1<<30)-1;
const int MAXN = 0;
const int MOD = 1e9 + 9;

int valid(int n, int v[]){
    int cur = -1;
    unordered_set<int> s;
    for(int i = 0; i < n; i++){
        if(s.count(v[i]))
            return 0;
        s.insert(v[i]);
        if(cur==-1){
            if(v[i] <= n)
                cur = v[i];
        }
        if(cur!=-1){
            if(v[i] <= n){
                if(cur!=v[i])
                    return 0;
            }
            cur++;
            if(cur==n+1)
                cur-=n;
        }
    }
    return 1;
}
int replacement(int n, int v[], int resp[]){

    int vproper[n];
    int refid = -1, refv; 
    int r;
    map<int,int> m;
    for(int i = 0; i < n; i++){
        if(v[i] > n){
            m.insert({v[i],i});
        } else if(refid==-1){
            refid = i;
            refv = v[i]-1;
        }
    }
    if(refid==-1){
        refv = 0;
        refid = 0;
    }
    refid-=refv;
    for(int i = 0; i < n; i++){
        vproper[i] = (i-refid+n)%n + 1;
    }
    int ptr = 0;

    for(int i = n+1; i <=( m.empty() ? 0 : m.rbegin()->first); i++){
        
        if(m.count(i)){
            resp[ptr++] = vproper[m[i]];
            vproper[m[i]] = i;
            m.erase(i);

        }else {
            resp[ptr++] = vproper[m.rbegin()->second];
            vproper[m.rbegin()->second] = i;
        }
        //cerr << (m.empty()) << endl;
    }
    return ptr;
}

inline long long power(ll a, ll b){
    ll ret = 1;
    while(b>0){
        if(b&1){
            ret *= a;
            ret%=MOD;
        }
        a*=a;
        a%=MOD;
        b>>=1;
    }
    return ret;
}

int countReplacement(int n, int v[]){
    if(!valid(n,v))
        return 0;
    
    set<int> s;
    for(int i = 0; i < n; i++){
        if(v[i] > n)
            s.insert(v[i]);
    }
    ll resp = 1;
    int cur = n+1;
    while(!s.empty()){
        auto it = s.begin();
        resp*= power(s.size(), *it-cur);
        resp%=MOD;
        cur = *it+1;
        s.erase(it);
    }
    return  resp;
}

/*int main(){
    int n;
    cin >> n;
    int v[n];
    int v2[n];
    for(int i = 0; i < n; i++) 
        cin >> v[i];
    int a = replacement(n,v,v2);
    //cout << a << '\n';
    for(int i = 0; i < a; i++){
        cout << v2[i] << ' ';
    }
}*/

Compilation message (stderr)

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:43:9: warning: unused variable 'r' [-Wunused-variable]
   43 |     int r;
      |         ^

• 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: 15 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10