답안 #8541 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
8541	2014-09-16T06:11:10 Z	gs14004	곤돌라 (IOI14_gondola)	C++	90 / 100	24 ms	3856 KB

gondola

#include <cstdio>
#include <algorithm>
#include <queue>
#include <utility>
#include <cstdlib>
#include "gondola.h"
using namespace std;
typedef pair<int,int> pi;

int valid(int n, int inputSeq[]){
    int v[250005]={};
    for (int i=0; i<n; i++) {
        if(v[inputSeq[i]]) return 0;
        v[inputSeq[i]] = 1;
    }
    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){
    if(time < 0) return 1ll;
    long long res = 1, piv = x;
    while (time) {
        if(time&1) res *= piv;
        piv *= piv;
        res %= 1000000009ll;
        piv %= 1000000009ll;
        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 %= 1000000009ll;
    }
    if(newSeq[piv-1] > 98765321 && n > 40000){
        puts("sex");
        exit(0);
    }
    return res;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	3848 KB	Output is correct
2	Correct	3848 KB	Output is correct
3	Correct	3848 KB	Output is correct
4	Correct	3848 KB	Output is correct
5	Correct	3852 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3848 KB	Output is correct
2	Correct	0 ms	3852 KB	Output is correct
3	Correct	0 ms	3852 KB	Output is correct
4	Correct	0 ms	3852 KB	Output is correct
5	Correct	0 ms	3848 KB	Output is correct
6	Correct	4 ms	3856 KB	Output is correct
7	Correct	12 ms	3848 KB	Output is correct
8	Correct	8 ms	3852 KB	Output is correct
9	Correct	4 ms	3848 KB	Output is correct
10	Correct	12 ms	3852 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3848 KB	Output is correct
2	Correct	0 ms	3852 KB	Output is correct
3	Correct	0 ms	3856 KB	Output is correct
4	Correct	0 ms	3856 KB	Output is correct
5	Correct	0 ms	3852 KB	Output is correct
6	Correct	4 ms	3848 KB	Output is correct
7	Correct	12 ms	3848 KB	Output is correct
8	Correct	12 ms	3848 KB	Output is correct
9	Correct	4 ms	3852 KB	Output is correct
10	Correct	12 ms	3852 KB	Output is correct
11	Correct	0 ms	3852 KB	Output is correct
12	Correct	0 ms	3848 KB	Output is correct
13	Correct	0 ms	3852 KB	Output is correct
14	Correct	0 ms	3848 KB	Output is correct
15	Correct	8 ms	3852 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	3000 KB	Output is correct
2	Correct	3000 KB	Output is correct
3	Correct	3000 KB	Output is correct
4	Correct	3000 KB	Output is correct
5	Correct	3000 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	3000 KB	Output is correct
2	Correct	3000 KB	Output is correct
3	Correct	3000 KB	Output is correct
4	Correct	3000 KB	Output is correct
5	Correct	3000 KB	Output is correct
6	Correct	3000 KB	Output is correct
7	Correct	3000 KB	Output is correct
8	Correct	3000 KB	Output is correct
9	Correct	3000 KB	Output is correct
10	Correct	3000 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3000 KB	Output is correct
2	Correct	0 ms	3000 KB	Output is correct
3	Correct	0 ms	3000 KB	Output is correct
4	Correct	0 ms	3000 KB	Output is correct
5	Correct	0 ms	3000 KB	Output is correct
6	Correct	0 ms	3000 KB	Output is correct
7	Correct	0 ms	3000 KB	Output is correct
8	Correct	0 ms	3000 KB	Output is correct
9	Correct	0 ms	3000 KB	Output is correct
10	Correct	0 ms	3000 KB	Output is correct
11	Correct	12 ms	3000 KB	Output is correct
12	Correct	12 ms	3000 KB	Output is correct
13	Correct	12 ms	3388 KB	Output is correct
14	Correct	8 ms	3000 KB	Output is correct
15	Correct	24 ms	3388 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	3856 KB	Output is correct
2	Correct	3848 KB	Output is correct
3	Correct	3848 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	메모리	Grader output
1	Correct	3852 KB	Output is correct
2	Correct	3852 KB	Output is correct
3	Correct	3852 KB	Output is correct
4	Correct	3848 KB	Output is correct
5	Correct	3848 KB	Output is correct
6	Correct	3848 KB	Output is correct
7	Correct	3848 KB	Output is correct
8	Correct	3852 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3852 KB	Output is correct
2	Correct	0 ms	3848 KB	Output is correct
3	Correct	0 ms	3852 KB	Output is correct
4	Correct	0 ms	3852 KB	Output is correct
5	Correct	0 ms	3852 KB	Output is correct
6	Correct	0 ms	3856 KB	Output is correct
7	Correct	0 ms	3856 KB	Output is correct
8	Correct	0 ms	3856 KB	Output is correct
9	Correct	8 ms	3852 KB	Output is correct
10	Correct	8 ms	3852 KB	Output is correct
11	Correct	4 ms	3852 KB	Output is correct
12	Correct	4 ms	3852 KB	Output is correct
13	Correct	0 ms	3852 KB	Output is correct

Subtask #10
0.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	3848 KB	Output is correct
2	Correct	0 ms	3852 KB	Output is correct
3	Correct	0 ms	3848 KB	Output is correct
4	Correct	0 ms	3852 KB	Output is correct
5	Correct	0 ms	3852 KB	Output is correct
6	Correct	0 ms	3848 KB	Output is correct
7	Correct	0 ms	3852 KB	Output is correct
8	Correct	0 ms	3852 KB	Output is correct
9	Correct	4 ms	3848 KB	Output is correct
10	Correct	4 ms	3852 KB	Output is correct
11	Correct	4 ms	3856 KB	Output is correct
12	Correct	8 ms	3852 KB	Output is correct
13	Correct	0 ms	3848 KB	Output is correct
14	Runtime error	12 ms	3844 KB	SIGSEGV Segmentation fault
15	Halted	0 ms	0 KB	-

답안 #8541

Compilation message