답안 #73289 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
73289	2018-08-28T06:44:53 Z	Batmend4	곤돌라 (IOI14_gondola)	C++	60 / 100	35 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;
    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 *= n;
        n %= 1000000009;
    }
    return s;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	248 KB	Output is correct
2	Correct	3 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	3 ms	520 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	520 KB	Output is correct
2	Correct	3 ms	520 KB	Output is correct
3	Correct	2 ms	548 KB	Output is correct
4	Correct	2 ms	552 KB	Output is correct
5	Correct	2 ms	592 KB	Output is correct
6	Correct	9 ms	872 KB	Output is correct
7	Correct	18 ms	1220 KB	Output is correct
8	Correct	18 ms	1220 KB	Output is correct
9	Correct	8 ms	1220 KB	Output is correct
10	Correct	27 ms	1256 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	1256 KB	Output is correct
2	Correct	2 ms	1256 KB	Output is correct
3	Correct	3 ms	1256 KB	Output is correct
4	Correct	3 ms	1256 KB	Output is correct
5	Correct	2 ms	1256 KB	Output is correct
6	Correct	10 ms	1256 KB	Output is correct
7	Correct	17 ms	1256 KB	Output is correct
8	Correct	14 ms	1256 KB	Output is correct
9	Correct	9 ms	1256 KB	Output is correct
10	Correct	17 ms	1276 KB	Output is correct
11	Correct	3 ms	1276 KB	Output is correct
12	Correct	3 ms	1276 KB	Output is correct
13	Correct	35 ms	2544 KB	Output is correct
14	Correct	2 ms	2544 KB	Output is correct
15	Correct	30 ms	2544 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2600 KB	Output is correct
2	Correct	4 ms	2600 KB	Output is correct
3	Correct	2 ms	2600 KB	Output is correct
4	Correct	4 ms	2600 KB	Output is correct
5	Incorrect	3 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	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 #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2600 KB	Output is correct
2	Correct	3 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	-

답안 #73289

Compilation message