답안 #73296 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73296	2018-08-28T06:54:20 Z	Batmend4	곤돌라 (IOI14_gondola)	C++	100 / 100	121 ms	9724 KB

gondola

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

long long power( int x, int e ){
    long long _pos = x;
    long long _s = 1;
    while( e ){
        int a = e % 2;
        if( a == 1 ){
            _s *= _pos;
            _s %= 1000000009;
        }
        _pos *= _pos;
        _pos %= 1000000009;
        e /= 2;
    }
    return _s;
}

int valid(int n, int inputSeq[])
{
    map< int, bool> m;
    bool lol = 1;
    int ind = -1;
    for( int i = 0 ; i < n ; i++ ){
        if( inputSeq[i] <= n ){
            lol = 0;
            ind = i;
        }
        if( inputSeq[i] > n ){
            if( m[inputSeq[i]] == 1 ) return 0;
            m[inputSeq[i]] = 1;
        }
    }
    if( lol == 1 ){
        return 1;
    }
    int ct[n + 5];
    int nn = n + inputSeq[ind] - 1 - ind;
    for( int i = 0 ; i < n ; i++ ){
        ct[(nn + i) % n] = inputSeq[i];
    }
    
    for( int i = 0 ; i < n ; i++ ){
        if( ct[i] <= n ){
            if( i != ct[i] - 1 ){
                return 0;
            }
        }
    }
    return 1;
}

//----------------------

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
    int ind = -1;
    int ct[n + 5];
    vector< pair<int, int> >v;
    for( int i = 0 ; i < n ; i++ ){
        if( gondolaSeq[i] <= n ){
            ind = i;
        }
    }
    int nn = n + gondolaSeq[ind] - 1 - ind;
    for( int i = 0 ; i < n ; i++ ){
        ct[(nn + i) % n] = gondolaSeq[i];
    }
    for( int i = 0 ; i < n ; i++ ){
        v.push_back( make_pair(ct[i], i));
    }
    sort( v.begin(), v.end());
    
    int pos = 0;
    for( int i = 0 ; i < n ; i++ ){
        int ct1 = v[i].first;
        if( ct1 <= n ) continue;
        if( i == 0 ){
            replacementSeq[pos] = v[0].second + 1;
            pos++;
            for( int ii = n + 1 ; ii < v[0].first ; ii++ ){
                replacementSeq[pos] = ii;
                pos++;
            }
            continue;
        }
        if( v[i - 1].first <= n ){
            replacementSeq[pos] = v[i].second + 1;
            pos++;
            for( int ii = n + 1 ; ii < v[i].first ; ii++ ){
                replacementSeq[pos] = ii;
                pos++;
            }
            continue;
        }
        replacementSeq[pos] = v[i].second + 1;
        pos++;
        for( int ii = v[i-1].first + 1 ; ii < v[i].first ; ii++ ){
            replacementSeq[pos] = ii;
            pos++;
        }
        
    }
    return pos;
}

//----------------------

int countReplacement(int n, int inputSeq[])
{
    if( valid( n, inputSeq) != 1 ){
        return 0;
    }
    vector<int> v;
    bool lol = 1;
    bool fuck = 1;
    for( int i = 0 ; i < n ; i++ ){
        if( inputSeq[i] > n ) lol = 0;
        if( inputSeq[i] <= n ) fuck = 0;
        v.push_back(inputSeq[i]);
    }
    if( lol == 1 ) return 1;
    sort( v.begin(), v.end());
    
    long long s = 1;
    int pos = n + 1;
    for( int i = 0 ; i < n ; i++){
        if( v[i] <= n ) continue;
        s *= power( n - i, v[i] - pos );
        s %= 1000000009;
        pos = v[i] + 1;
    }
    if( fuck == 1 ){
        s *= (long long)n;
        s %= 1000000009;
    }
    return s;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	560 KB	Output is correct
2	Correct	3 ms	560 KB	Output is correct
3	Correct	3 ms	560 KB	Output is correct
4	Correct	2 ms	560 KB	Output is correct
5	Correct	2 ms	560 KB	Output is correct
6	Correct	10 ms	876 KB	Output is correct
7	Correct	17 ms	1388 KB	Output is correct
8	Correct	14 ms	1388 KB	Output is correct
9	Correct	5 ms	1388 KB	Output is correct
10	Correct	20 ms	1388 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2428 KB	Output is correct
2	Correct	2 ms	2428 KB	Output is correct
3	Correct	2 ms	2428 KB	Output is correct
4	Correct	2 ms	2428 KB	Output is correct
5	Correct	2 ms	2428 KB	Output is correct
6	Correct	3 ms	2428 KB	Output is correct
7	Correct	3 ms	2428 KB	Output is correct
8	Correct	3 ms	2428 KB	Output is correct
9	Correct	3 ms	2428 KB	Output is correct
10	Correct	3 ms	2428 KB	Output is correct
11	Correct	17 ms	2428 KB	Output is correct
12	Correct	19 ms	2468 KB	Output is correct
13	Correct	20 ms	2468 KB	Output is correct
14	Correct	15 ms	2468 KB	Output is correct
15	Correct	31 ms	2520 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2520 KB	Output is correct
2	Correct	3 ms	2520 KB	Output is correct
3	Correct	3 ms	2520 KB	Output is correct
4	Correct	2 ms	2520 KB	Output is correct
5	Correct	2 ms	2520 KB	Output is correct
6	Correct	3 ms	2520 KB	Output is correct
7	Correct	2 ms	2520 KB	Output is correct
8	Correct	2 ms	2520 KB	Output is correct
9	Correct	70 ms	4456 KB	Output is correct
10	Correct	46 ms	4456 KB	Output is correct
11	Correct	24 ms	4456 KB	Output is correct
12	Correct	24 ms	4456 KB	Output is correct
13	Correct	6 ms	4456 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	4456 KB	Output is correct
2	Correct	2 ms	4456 KB	Output is correct
3	Correct	2 ms	4456 KB	Output is correct
4	Correct	2 ms	4456 KB	Output is correct
5	Correct	2 ms	4456 KB	Output is correct
6	Correct	2 ms	4456 KB	Output is correct
7	Correct	3 ms	4456 KB	Output is correct
8	Correct	3 ms	4456 KB	Output is correct
9	Correct	65 ms	5712 KB	Output is correct
10	Correct	47 ms	5712 KB	Output is correct
11	Correct	21 ms	5712 KB	Output is correct
12	Correct	24 ms	5712 KB	Output is correct
13	Correct	8 ms	5712 KB	Output is correct
14	Correct	94 ms	8384 KB	Output is correct
15	Correct	121 ms	9724 KB	Output is correct
16	Correct	19 ms	9724 KB	Output is correct
17	Correct	69 ms	9724 KB	Output is correct
18	Correct	38 ms	9724 KB	Output is correct

답안 #73296

Compilation message