oj.uz

Submission #7316

# Submission time Handle Problem Language Result Execution time Memory
7316 2014-07-31T07:24:17 Z myungwoo Gondola (IOI14_gondola) C++
100 / 100
 48 ms 4556 KB 
#include <map>
#include <vector>
#include <algorithm>
#include "gondola.h"
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 = n,last = n,i;
    vector <int> a;
    for (i=0;i<n;i++){
        if (inputSeq[i] <= n) ret = 1;
        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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 8 ms 2972 KB Output is correct
7 Correct 16 ms 2972 KB Output is correct
8 Correct 12 ms 2972 KB Output is correct
9 Correct 4 ms 2972 KB Output is correct
10 Correct 12 ms 2972 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 4 ms 2972 KB Output is correct
7 Correct 12 ms 2972 KB Output is correct
8 Correct 16 ms 2972 KB Output is correct
9 Correct 4 ms 2972 KB Output is correct
10 Correct 20 ms 2972 KB Output is correct
11 Correct 0 ms 2972 KB Output is correct
12 Correct 0 ms 2972 KB Output is correct
13 Correct 0 ms 2972 KB Output is correct
14 Correct 0 ms 2972 KB Output is correct
15 Correct 8 ms 2972 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 0 ms 2972 KB Output is correct
7 Correct 0 ms 2972 KB Output is correct
8 Correct 0 ms 2972 KB Output is correct
9 Correct 0 ms 2972 KB Output is correct
10 Correct 0 ms 2972 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 0 ms 2972 KB Output is correct
7 Correct 0 ms 2972 KB Output is correct
8 Correct 0 ms 2972 KB Output is correct
9 Correct 0 ms 2972 KB Output is correct
10 Correct 0 ms 2972 KB Output is correct
11 Correct 12 ms 2972 KB Output is correct
12 Correct 20 ms 2972 KB Output is correct
13 Correct 36 ms 4556 KB Output is correct
14 Correct 12 ms 2972 KB Output is correct
15 Correct 40 ms 3632 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 0 ms 2972 KB Output is correct
7 Correct 0 ms 2972 KB Output is correct
8 Correct 0 ms 2972 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 0 ms 2972 KB Output is correct
7 Correct 0 ms 2972 KB Output is correct
8 Correct 0 ms 2972 KB Output is correct
9 Correct 36 ms 3360 KB Output is correct
10 Correct 28 ms 3360 KB Output is correct
11 Correct 12 ms 3100 KB Output is correct
12 Correct 16 ms 3100 KB Output is correct
13 Correct 0 ms 2972 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2972 KB Output is correct
2 Correct 0 ms 2972 KB Output is correct
3 Correct 0 ms 2972 KB Output is correct
4 Correct 0 ms 2972 KB Output is correct
5 Correct 0 ms 2972 KB Output is correct
6 Correct 0 ms 2972 KB Output is correct
7 Correct 0 ms 2972 KB Output is correct
8 Correct 0 ms 2972 KB Output is correct
9 Correct 36 ms 3360 KB Output is correct
10 Correct 28 ms 3360 KB Output is correct
11 Correct 12 ms 3100 KB Output is correct
12 Correct 16 ms 3100 KB Output is correct
13 Correct 4 ms 2972 KB Output is correct
14 Correct 44 ms 3744 KB Output is correct
15 Correct 48 ms 3744 KB Output is correct
16 Correct 8 ms 3100 KB Output is correct
17 Correct 40 ms 3360 KB Output is correct
18 Correct 20 ms 3360 KB Output is correct