답안 #73282 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73282	2018-08-28T06:36:22 Z	Batmend4	곤돌라 (IOI14_gondola)	C++	60 / 100	37 ms	2600 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 *= x;
        _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;
    for( int i = 0 ; i < n ; i++ ){
        if( inputSeq[i] > n ) lol = 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;
    }
    return s;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct
4	Correct	3 ms	620 KB	Output is correct
5	Correct	3 ms	620 KB	Output is correct
6	Correct	13 ms	828 KB	Output is correct
7	Correct	18 ms	1260 KB	Output is correct
8	Correct	15 ms	1260 KB	Output is correct
9	Correct	7 ms	1260 KB	Output is correct
10	Correct	19 ms	1276 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	1276 KB	Output is correct
2	Correct	2 ms	1276 KB	Output is correct
3	Correct	3 ms	1276 KB	Output is correct
4	Correct	3 ms	1276 KB	Output is correct
5	Correct	2 ms	1276 KB	Output is correct
6	Correct	8 ms	1276 KB	Output is correct
7	Correct	20 ms	1276 KB	Output is correct
8	Correct	14 ms	1276 KB	Output is correct
9	Correct	5 ms	1276 KB	Output is correct
10	Correct	22 ms	1276 KB	Output is correct
11	Correct	3 ms	1276 KB	Output is correct
12	Correct	2 ms	1276 KB	Output is correct
13	Correct	29 ms	2436 KB	Output is correct
14	Correct	3 ms	2436 KB	Output is correct
15	Correct	37 ms	2436 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2436 KB	Output is correct
2	Correct	2 ms	2436 KB	Output is correct
3	Correct	2 ms	2436 KB	Output is correct
4	Correct	2 ms	2436 KB	Output is correct
5	Correct	3 ms	2436 KB	Output is correct
6	Correct	3 ms	2436 KB	Output is correct
7	Correct	3 ms	2436 KB	Output is correct
8	Correct	4 ms	2436 KB	Output is correct
9	Correct	5 ms	2436 KB	Output is correct
10	Correct	3 ms	2436 KB	Output is correct
11	Correct	22 ms	2564 KB	Output is correct
12	Correct	18 ms	2564 KB	Output is correct
13	Correct	21 ms	2564 KB	Output is correct
14	Correct	18 ms	2564 KB	Output is correct
15	Correct	26 ms	2600 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2600 KB	Output is correct
2	Correct	3 ms	2600 KB	Output is correct
3	Correct	3 ms	2600 KB	Output is correct
4	Correct	3 ms	2600 KB	Output is correct
5	Incorrect	2 ms	2600 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #9
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2600 KB	Output is correct
2	Correct	2 ms	2600 KB	Output is correct
3	Correct	2 ms	2600 KB	Output is correct
4	Correct	2 ms	2600 KB	Output is correct
5	Incorrect	2 ms	2600 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2600 KB	Output is correct
2	Correct	2 ms	2600 KB	Output is correct
3	Correct	3 ms	2600 KB	Output is correct
4	Correct	2 ms	2600 KB	Output is correct
5	Incorrect	3 ms	2600 KB	Output isn't correct
6	Halted	0 ms	0 KB	-

답안 #73282

Compilation message