답안 #70825 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70825	2018-08-23T13:48:38 Z	yusufake	곤돌라 (IOI14_gondola)	C++	65 / 100	130 ms	14264 KB

gondola

#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"

#define mp make_pair
#define st first
#define nd second
#define ll long long
const int mod = 1e9 + 9;
const int N   = 2e5 + 5;
pair < int , int > mn;
int T[N];
int valid(int n, int *A){
    int i;
    mn = mp(mod,0);
    map < int , int > M;
    M.clear();
    for(i=0;i<n;i++){
        mn = min(mn , mp(A[i],i));
        if(M[ A[i] ]) return 0;
        M[ A[i] ] = 1;
    }
    if(mn.st > n) return 1;
    int j = mn.nd - mn.st+1;
    if(j < 0) j += n;
    for(i=0;i<n;i++)
        if(A[i] <= n && ((j+A[i]-1 < n && j+A[i]-1 != i)||(j+A[i]-1 >= n && j+A[i]-1-n != i)) )
            return 0;
    return 1;
}

ll fast(ll a, ll b){
    ll t=1;
    for(; b ; b>>=1){
        if(b & 1) t = t*a % mod;
        a = a*a % mod;
    }
    return t;
}

int countReplacement(int n, int *A){
    if(valid(n,A) == 0) return 0;
    long long ans=1;
    int i,x,y;
    for(i=0;i<n;i++) T[i] = A[i];
    sort(T,T+n);
    for(i=n-1;i>=0;i--){
        x = T[i];
        if(x <= n) break;
        y = i && T[i-1] > n ? T[i-1] : n;
        ans = ans * fast(n-i,x-y-1) % mod;
    }
    if(i == -1) ans = ans * n % mod;
    return ans;
}

int replacement(int n, int *A, int *B){
    return 0;
    if(valid(n,A) == 0) return 0;
    countReplacement(n,A);
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	3 ms	548 KB	Output is correct
4	Correct	3 ms	548 KB	Output is correct
5	Correct	2 ms	548 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	548 KB	Output is correct
2	Correct	2 ms	580 KB	Output is correct
3	Correct	2 ms	592 KB	Output is correct
4	Correct	3 ms	724 KB	Output is correct
5	Correct	3 ms	724 KB	Output is correct
6	Correct	29 ms	2768 KB	Output is correct
7	Correct	17 ms	2768 KB	Output is correct
8	Correct	40 ms	5464 KB	Output is correct
9	Correct	17 ms	5464 KB	Output is correct
10	Correct	67 ms	6524 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	6524 KB	Output is correct
2	Correct	2 ms	6524 KB	Output is correct
3	Correct	3 ms	6524 KB	Output is correct
4	Correct	3 ms	6524 KB	Output is correct
5	Correct	2 ms	6524 KB	Output is correct
6	Correct	24 ms	6524 KB	Output is correct
7	Correct	20 ms	6524 KB	Output is correct
8	Correct	43 ms	7164 KB	Output is correct
9	Correct	16 ms	7164 KB	Output is correct
10	Correct	53 ms	8428 KB	Output is correct
11	Correct	2 ms	8428 KB	Output is correct
12	Correct	2 ms	8428 KB	Output is correct
13	Correct	31 ms	8428 KB	Output is correct
14	Correct	3 ms	8428 KB	Output is correct
15	Correct	83 ms	9320 KB	Output is correct

Subtask #4
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	9320 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	2 ms	9320 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	9320 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9320 KB	Output is correct
2	Correct	2 ms	9320 KB	Output is correct
3	Correct	2 ms	9320 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	9320 KB	Output is correct
2	Correct	3 ms	9320 KB	Output is correct
3	Correct	4 ms	9320 KB	Output is correct
4	Correct	3 ms	9320 KB	Output is correct
5	Correct	2 ms	9320 KB	Output is correct
6	Correct	2 ms	9320 KB	Output is correct
7	Correct	2 ms	9320 KB	Output is correct
8	Correct	3 ms	9320 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9320 KB	Output is correct
2	Correct	2 ms	9320 KB	Output is correct
3	Correct	3 ms	9320 KB	Output is correct
4	Correct	2 ms	9320 KB	Output is correct
5	Correct	2 ms	9320 KB	Output is correct
6	Correct	3 ms	9320 KB	Output is correct
7	Correct	2 ms	9320 KB	Output is correct
8	Correct	2 ms	9320 KB	Output is correct
9	Correct	61 ms	9420 KB	Output is correct
10	Correct	66 ms	9420 KB	Output is correct
11	Correct	24 ms	9420 KB	Output is correct
12	Correct	26 ms	9420 KB	Output is correct
13	Correct	7 ms	9420 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	9420 KB	Output is correct
2	Correct	3 ms	9420 KB	Output is correct
3	Correct	3 ms	9420 KB	Output is correct
4	Correct	4 ms	9420 KB	Output is correct
5	Correct	2 ms	9420 KB	Output is correct
6	Correct	2 ms	9420 KB	Output is correct
7	Correct	3 ms	9420 KB	Output is correct
8	Correct	2 ms	9420 KB	Output is correct
9	Correct	71 ms	10572 KB	Output is correct
10	Correct	60 ms	10572 KB	Output is correct
11	Correct	23 ms	10572 KB	Output is correct
12	Correct	26 ms	10572 KB	Output is correct
13	Correct	7 ms	10572 KB	Output is correct
14	Correct	130 ms	12812 KB	Output is correct
15	Correct	121 ms	14264 KB	Output is correct
16	Correct	16 ms	14264 KB	Output is correct
17	Correct	76 ms	14264 KB	Output is correct
18	Correct	33 ms	14264 KB	Output is correct

답안 #70825

Compilation message