Submission #103764

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
103764	2019-04-02T13:03:57 Z	SecretAgent007	Gondola (IOI14_gondola)	C++17	Compilation error	0 ms	0 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[]){

    int index = 0;
    int num = n;

    map< int, bool> visited;

    for(int i = 0; i < n; i++){
        if(visited[inputSeq[i]]) return 0;
        visited[inputSeq[i]] = true;
        if(inputSeq[i] <= num){
            num = inputSeq[i];
            index = i;
        }
    }

    int start = (index-num+1+n)%n;

    int curr = 1;

    for(int i = start; i < n; i++){
        if(inputSeq[i] <= n && inputSeq[i] != curr) return 0;
        curr++;
    }
    for(int j = 0; j < start; j++){
        if(inputSeq[j] <= n && inputSeq[j] != curr) return 0;
        curr++;
    }
    return 1;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int index = 0;
    int num = n;

    int maxi = 0;

    for(int i = 0; i < n; i++){
        if(gondolaSeq[i] <= num){
            num = gondolaSeq[i];
            index = i;
        }
        maxi = max(maxi, gondolaSeq[i]);
    }

    int start = (index-num+1+n)%n;

    if(gondolaSeq[index] > n) start = 0;

    int curr = 1;

    map<int, int> mape;

    vector< int > current(n+1);

    for(int i = 1; i <= n; i++){
        current[i] = i;
    }

    int in;

    for(int i = start; i < n; i++){
        mape[gondolaSeq[i]] = curr;
        if(gondolaSeq[i] == maxi) in = curr;
        curr++;
    }
    for(int j = 0; j < start; j++){
        mape[gondolaSeq[j]] = curr;
        if(gondolaSeq[j] == maxi) in = curr;
        curr++;
    }

    int c = 0;

    for(int i = n+1; i <= maxi; i++){
        if(mape[i] != 0){
            replacementSeq[c] = current[mape[i]];
            current[mape[i]] = i;
        }else{
            replacementSeq[c] = current[in];
            current[in] = i;
        }
        c++;
    }

    return c;
}

int last;

vector< int > memo;
map<int, bool> visited;
vector< int > ve;
vector< int > cnt;

const int mod = 1e9+9;

int dp(int curr, int n){
    if(curr >= last){
        return 1;
    }
    if(memo[curr] != -1) return memo[curr];

    memo[curr] = 0;

    if(visited[curr]){
        return memo[curr] = dp(curr+1,n);
    }

    long long  index = n-(lower_bound(cnt.begin(), cnt.end(), curr+1)-cnt.begin());
    long long nb = index;
    nb = nb%mod;

   // cout << curr << ' ' << nb << endl;
    /*
    for(int i = 0; i < n; i++){
        if(ve[i] > curr){
            memo[curr] += dp(curr+1,n);
            memo[curr] %= mod;
        }
    }
*/
    long long tempo = (nb*dp(curr+1,n))%mod;
    return memo[curr] = (tempo);
}

int countReplacement(int n, int inputSeq[]){
    if(!valid(n,inputSeq)) return 0;

    ve.resize(n);
    cnt.resize(n);

    int mini = INF;

    for(int i = 0; i < n; i++){
        mini = min(mini, inputSeq[i]);
        last = max(last, inputSeq[i]);
        ve[i] = inputSeq[i];
        cnt[i] = inputSeq[i];
        visited[inputSeq[i]] = true;
    }

    sort(cnt.begin(), cnt.end());

    memo.resize(last+1,-1);

    if(mini >= n){
        long long rep = dp(n+1,n);
        long long ans = ((long long)n*rep)%mod;
        return ans;
    }

    return dp(n+1, n);
}
/*
int main(){
    int n;
    cin >> n;
    int v[n];
    int maxi = 0;
    for(int i = 0; i < n; i++){
        cin >> v[i];
        maxi = max(maxi, v[i]);
    }
    int ans[maxi-n];
    cout << replacement(n,v,ans) << endl;
    for(int a : ans){
        cout << a << ' ';
    }
    cout << endl;

    cout << "NUMBER " << countReplacement(n,v) << endl;
}
*/

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:138:16: error: 'INF' was not declared in this scope
     int mini = INF;
                ^~~
gondola.cpp:138:16: note: suggested alternative: 'SING'
     int mini = INF;
                ^~~
                SING