oj.uz

Submission #8550

# Submission time Handle Problem Language Result Execution time Memory
8550 2014-09-16T06:21:58 Z gs14004 Gondola (IOI14_gondola) C++
60 / 100
 48 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, piv = time, mod = 1e9 + 9;
    while (time) {
        if(time&1) res *= piv;
        piv *= piv;
        res %= mod;
        piv %= mod;
        time >>= 1;
    }
    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 12 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 12 ms 4060 KB Output is correct
10 Correct 48 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 4 ms 3004 KB Output is correct
8 Correct 36 ms 6304 KB Output is correct
9 Correct 12 ms 4060 KB Output is correct
10 Correct 48 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 40 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 8 ms 3004 KB Output is correct
12 Correct 12 ms 3004 KB Output is correct
13 Correct 12 ms 3392 KB Output is correct
14 Correct 12 ms 3004 KB Output is correct
15 Correct 20 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
0.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 Incorrect 0 ms 3004 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0.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 Incorrect 0 ms 3004 KB Output isn't correct
6 Halted 0 ms 0 KB -

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 Incorrect 0 ms 3004 KB Output isn't correct
6 Halted 0 ms 0 KB -