답안 #7313

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
7313 2014-07-31T07:04:58 Z myungwoo 곤돌라 (IOI14_gondola) C++
컴파일 오류
0 ms 0 KB
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
 
#define MAXN 100000
#define pb push_back
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
typedef long long lld;
 
static const int MOD = 1e9 + 9;
static int tmp[MAXN];
 
int valid(int n,int inputSeq[])
{
    int i,j,p = -1;
    for (i=0;i<n;i++){
        tmp[i] = inputSeq[i];
        if (inputSeq[i] <= n){
            j = (i-inputSeq[i]+1+n)%n;
            if (p < 0) p = j;
            else if (p != j) return 0;
        }
    }
    sort(tmp,tmp+n);
    for (i=1;i<n;i++) if (tmp[i-1] == tmp[i]) return 0;
    return 1;
}
 
int replacement(int n,int gondolaSeq[],int replacementSeq[])
{
    if (!valid(n,gondolaSeq)) return -1;
    int i,j,p = -1;
    for (i=0;i<n;i++){
        if (gondolaSeq[i] <= n){
            j = (i-gondolaSeq[i]+1+n)%n;
            if (p < 0) p = j;
            else if (p != j) return 0;
        }
    }
    int y=0;
    for (i=0;i<n;i++) if (gondolaSeq[i] > n){
        if (y < gondolaSeq[i]) y = gondolaSeq[i];
    }
    if (!y) return 0;
    map<int,int> pos;
    for (i=0;i<n;i++) pos[gondolaSeq[i]] = i;
    if (p == -1) p = 0;
    int c = 0, t = pos[y];
    for (i=0;i<n;i++) tmp[i] = (i-p+n)%n+1;
    for (i=n+1;i<=y;i++){
        int x = pos.count(i) ? pos[i] : t;
        replacementSeq[c++] = tmp[x];
        tmp[x] = i;
    }
    return y-n;
}
 
int pow(int a,int b)
{
    int ret = 1,t = a,i;
    for (i=0;i<31;i++,t=(lld)t*t%MOD) if (b&(1<<i)){
        ret = (lld)ret*t%MOD;
    }
    return ret;
}
 
int countReplacement(int n,int inputSeq[])
{
    if (!valid(n,inputSeq)) return 0;
    int ret = 1,last = n,i;
    vector <int> a;
    for (i=0;i<n;i++){
        if (inputSeq[i] <= n) ret = n;
        else a.pb(inputSeq[i]);
    }
    sort(all(a));
    int left = sz(a);
    for (i=0;i<sz(a);i++){
        int dummy = a[i] - last - 1;
        ret = ((lld)ret*pow(left,dummy))%MOD;
        last = a[i]; left--;
    }
    return ret;
}

Compilation message

/tmp/ccyWbJSZ.o: In function `main':
grader.cpp:(.text.startup+0xb1): undefined reference to `replacement'
grader.cpp:(.text.startup+0x141): undefined reference to `countReplacement'
grader.cpp:(.text.startup+0x164): undefined reference to `valid'
collect2: ld returned 1 exit status