oj.uz

Submission #8549

# Submission time Handle Problem Language Result Execution time Memory
8549 2014-09-16T06:20:52 Z gs14004 Gondola (IOI14_gondola) C++
90 / 100
 1000 ms 6964 KB 
#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <set>
#include "gondola.h"

using namespace std;
typedef pair<int,int> pi;

int valid(int n, int inputSeq[]){
    set<int> s;
    for (int i=0; i<n; i++) {
        if(s.find(inputSeq[i]) != s.end()) return 0;
        s.insert(inputSeq[i]);
    }
    int piv = -1;
    for (int i=0; i<n; i++) {
        if(inputSeq[i] <= n){
            if(piv == -1){
                piv = i;
            }
            else{
                int res = i + (inputSeq[piv] - piv) + n;
                res %= n;
                if(res == 0) res = n;
                if(inputSeq[i] != res) return 0;
            }
        }
    }
    return 1;
}

priority_queue<pi,vector<pi>,greater<pi> > pq, pq2;

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
    int piv = 0, piv2 = n+1, piv3 = 0;
    for (int i=0; i<n; i++) {
        if(gondolaSeq[i] <= n){
            piv = gondolaSeq[i] - i - 1+ n;
            piv %= n;
        }
    }
    int newSeq[100005] = {};
    for (int i=0; i<n; i++) {
        newSeq[i] = gondolaSeq[(i + n - piv)%n];
        if(newSeq[i] > n) pq.push(pi(newSeq[i],i+1));
    }
    while (!pq.empty()) {
        pi x = pq.top();
        pq.pop();
        replacementSeq[piv3++] = x.second;
        for (int i=piv2; i<x.first; i++) {
            replacementSeq[piv3++] = i;
        }
        piv2 = x.first + 1;
    }
    return piv3;
}

long long pow(int x, int time){
    long long res = 1;
    for (int i=0; i<time; i++) {
        res *= x;
        res %= 1000000009;
    }
    return res;
}

int newSeq[100005];
int countReplacement(int n, int inputSeq[]){
    if(!valid(n,inputSeq)) return 0;
    int piv = 0, piv2 = n, cnt = 0;
    long long res = 1;
    for (int i=0; i<n; i++) {
        if(inputSeq[i] > n) newSeq[piv++] = inputSeq[i];
    }
    if(piv == n) res = piv;
    if(piv == 0) return 1;
    cnt = piv;
    sort(newSeq,newSeq+piv);
    for (int i=0; i<piv; i++) {
        res *= pow(cnt,newSeq[i] - piv2 - 1);
        piv2 = newSeq[i];
        cnt--;
        res %= 1000000009;
    }
    return (int)res;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 16 ms 4720 KB Output is correct
7 Correct 12 ms 3004 KB Output is correct
8 Correct 32 ms 6304 KB Output is correct
9 Correct 8 ms 4060 KB Output is correct
10 Correct 44 ms 6832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 20 ms 4720 KB Output is correct
7 Correct 12 ms 3004 KB Output is correct
8 Correct 32 ms 6304 KB Output is correct
9 Correct 8 ms 4060 KB Output is correct
10 Correct 40 ms 6832 KB Output is correct
11 Correct 0 ms 3004 KB Output is correct
12 Correct 0 ms 3004 KB Output is correct
13 Correct 16 ms 4588 KB Output is correct
14 Correct 0 ms 3004 KB Output is correct
15 Correct 56 ms 6964 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 0 ms 3004 KB Output is correct
7 Correct 0 ms 3004 KB Output is correct
8 Correct 0 ms 3004 KB Output is correct
9 Correct 48 ms 6436 KB Output is correct
10 Correct 36 ms 5776 KB Output is correct
11 Correct 12 ms 3928 KB Output is correct
12 Correct 12 ms 4192 KB Output is correct
13 Correct 4 ms 3268 KB Output is correct

Subtask #10
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3004 KB Output is correct
2 Correct 0 ms 3004 KB Output is correct
3 Correct 0 ms 3004 KB Output is correct
4 Correct 0 ms 3004 KB Output is correct
5 Correct 0 ms 3004 KB Output is correct
6 Correct 0 ms 3004 KB Output is correct
7 Correct 0 ms 3004 KB Output is correct
8 Correct 0 ms 3004 KB Output is correct
9 Correct 56 ms 6436 KB Output is correct
10 Correct 44 ms 5776 KB Output is correct
11 Correct 12 ms 3928 KB Output is correct
12 Correct 12 ms 4192 KB Output is correct
13 Correct 4 ms 3268 KB Output is correct
14 Execution timed out 1000 ms 6828 KB Program timed out
15 Halted 0 ms 0 KB -