oj.uz

Submission #7314

# Submission time Handle Problem Language Result Execution time Memory
7314 2014-07-31T07:06:01 Z myungwoo Gondola (IOI14_gondola) C++
55 / 100
 36 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 = 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;
}

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 4 ms 2972 KB Output is correct
7 Correct 8 ms 2972 KB Output is correct
8 Correct 20 ms 2972 KB Output is correct
9 Correct 4 ms 2972 KB Output is correct
10 Correct 24 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 8 ms 2972 KB Output is correct
7 Correct 12 ms 2972 KB Output is correct
8 Correct 8 ms 2972 KB Output is correct
9 Correct 0 ms 2972 KB Output is correct
10 Correct 16 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 4 ms 2972 KB Output is correct
14 Correct 0 ms 2972 KB Output is correct
15 Correct 16 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 16 ms 2972 KB Output is correct
12 Correct 24 ms 2972 KB Output is correct
13 Correct 36 ms 4556 KB Output is correct
14 Correct 8 ms 2972 KB Output is correct
15 Correct 36 ms 3632 KB Output is correct

Subtask #7
0.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2972 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2972 KB Output isn't correct
2 Halted 0 ms 0 KB -