답안 #252163

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
252163	2020-07-24T12:35:14 Z	Hehehe	곤돌라 (IOI14_gondola)	C++14	100 / 100	36 ms	3568 KB

gondola

#include<bits/stdc++.h> //:3
using namespace std;
typedef long long ll;
#define all(a) (a).begin(), (a).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define rc(s) return cout<<s,0
#define pi pair <int, int>
#define sz(x) (int)((x).size())
#include "gondola.h"

const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};

const ll inf = 2e9;
const ll mod = 1e9 + 9;
const int N = 2e5 + 11;
const ll INF64 = 3e18 + 1;
const double eps = 1e-14;
const double PI = acos(-1);

//ifstream in(".in");
//ofstream out(".out");

ll a[N];

ll poww(ll x, ll p){

    ll ans = 1;

    while(p){

        if(p % 2)ans = (ans * x * 1ll) % mod, ans = (ans + mod) % mod;

        x = (x * x * 1ll) % mod;

        p /= 2;
    }

    return (ans + mod) % mod;
}

int valid(int n, int x[]){

    ll j = -1;

    for(int i = 0; i < n; i++){
        a[i] = x[i] - 1;
        if(a[i] >= n)continue;
        j = i;
    }

    for(int i = 0; i < n; i++){

        if(i == j)continue;

        ll diff = j - i;

        ll val = (a[j] - diff + n) % n;

        if(a[i] < n && a[i] != val)return 0;
    }

    sort(a, a + n);

    for(int i = 1; i < n; i++){
        if(a[i] == a[i - 1])return 0;
    }

    return 1;
}

int replacement(int n, int x[], int y[]){

    vector<pi>t;

    int j = 0;

    for(int i = 0; i < n; i++){
        if(x[i] > n){
            t.push_back({x[i], i});
        }else j = i;
    }

    if(sz(t) == n)x[0] = 1;

    sort(all(t));

    for(int i = 0; i < n; i++){

        if(i > j){
            int val = x[j] + (i - j);
            if(val > n)val -= n;
            x[i] = val;
        }else{
            int val = x[j] - (j - i);
            if(val < 1)val += n;
            x[i] = val;
        }
    }

    vector<ll>ans;

    ll k = n;
    for(int i = 0; i < sz(t); i++){
        int num = t[i].ff, idx = t[i].ss;

        ans.push_back(x[idx]);

        for(int j = k + 1; j < num; j++)ans.push_back(j);

        k = num;
    }

    for(int i = 0; i < sz(ans); i++)y[i] = ans[i];

    return sz(ans);
}


int countReplacement(int n, int x[]){

    bool X = valid(n, x);

    if(!X)return 0;

    ll ans = 1;

    vector<ll>t;
    for(int i = 0; i < n; i++){
        if(x[i] > n)t.push_back(x[i]);
    }

    sort(all(t));

    ll prev = n;
    for(int i = 0; i < sz(t); i++){

        ll pozitiiDisponibile = sz(t) - i;
        ll numereDisponibile = t[i] - 1 - prev;

        ans = (ans * poww(pozitiiDisponibile, numereDisponibile)) % mod;
        ans = (ans + mod) % mod;

        prev = t[i];
    }

    if(sz(t) == n){
        ans = (ans * n) % mod;
        ans = (ans + mod) % mod;
    }

    return (ans + mod) % mod;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	9 ms	768 KB	Output is correct
7	Correct	14 ms	1408 KB	Output is correct
8	Correct	14 ms	1152 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	19 ms	1280 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	1 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	8 ms	768 KB	Output is correct
7	Correct	13 ms	1408 KB	Output is correct
8	Correct	15 ms	1152 KB	Output is correct
9	Correct	6 ms	640 KB	Output is correct
10	Correct	20 ms	1280 KB	Output is correct
11	Correct	0 ms	256 KB	Output is correct
12	Correct	1 ms	256 KB	Output is correct
13	Correct	6 ms	768 KB	Output is correct
14	Correct	0 ms	256 KB	Output is correct
15	Correct	14 ms	1280 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	512 KB	Output is correct
8	Correct	1 ms	512 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	508 KB	Output is correct
11	Correct	11 ms	640 KB	Output is correct
12	Correct	12 ms	640 KB	Output is correct
13	Correct	18 ms	1912 KB	Output is correct
14	Correct	11 ms	640 KB	Output is correct
15	Correct	25 ms	2676 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 ms	256 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	256 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	24 ms	1788 KB	Output is correct
10	Correct	20 ms	1660 KB	Output is correct
11	Correct	8 ms	1152 KB	Output is correct
12	Correct	9 ms	1280 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	256 KB	Output is correct
2	Correct	0 ms	384 KB	Output is correct
3	Correct	0 ms	256 KB	Output is correct
4	Correct	0 ms	256 KB	Output is correct
5	Correct	0 ms	256 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	256 KB	Output is correct
8	Correct	0 ms	256 KB	Output is correct
9	Correct	24 ms	1788 KB	Output is correct
10	Correct	19 ms	1660 KB	Output is correct
11	Correct	8 ms	1152 KB	Output is correct
12	Correct	10 ms	1152 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct
14	Correct	32 ms	3312 KB	Output is correct
15	Correct	36 ms	3568 KB	Output is correct
16	Correct	7 ms	1152 KB	Output is correct
17	Correct	24 ms	2300 KB	Output is correct
18	Correct	14 ms	1788 KB	Output is correct

답안 #252163

Compilation message