oj.uz

답안 #242446

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
242446 2020-06-27T17:18:11 Z joseacaz 곤돌라 (IOI14_gondola) C++17
90 / 100
 1000 ms 10188 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define pb push_back
#define all(x) x.begin(), x.end()

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

const int MAXN = 1e6 + 5;
vi input;
unordered_map<int, int> vis;

int valid(int N, int inputSeq[])
{
    input.clear();
    for(int i = 0; i < N; i++)
        input.pb(inputSeq[i]);
    
    int ans = 0, one = 0;
    vis.clear();
    for(int i = 0; i < N; i++)
    {
        if(vis[input[i]])
            return 0;
        vis[input[i]]++;
    }
    for(int i = 0; i < N; i++)
    {
        if(input[i] <= N)
        {
            one = 1;
            int idx;
            for(int j = 0; j < N; j++)
            {
                idx = (i + (j + 1 - input[i]) + N) % N;
                if(input[idx] == j + 1 || input[idx] > N)
                    ans++;
            }
            cerr << i << " " << input[i] << " " << ans << "\n";
            break;
        }
    }
    
    if(!one)
        return 1;
    return (ans == N);
}

int replacement(int N, int gondolaSeq[], int replacementSeq[])
{
    input.clear();
    for(int i = 0; i < N; i++)
        input.pb(gondolaSeq[i]);
    
    int one = 0;
    for(int i = 0; i < N; i++)
        if(input[i] <= N)
            one = (i - input[i] + 1 + N) % N;
    
    vpi seq;
    for(int i = 0; i < N; i++)
        seq.pb({input[(one + i) % N], i + 1});
    sort(all(seq));
    int curr = 0, newGondola = N + 1;
    for(int i = 0; i < N; i++)
    {
        while(seq[i].second != seq[i].first)
        {
            replacementSeq[curr++] = seq[i].second;
            seq[i].second = newGondola++;
        }
    }
    return curr;
}

const ll MOD = 1e9 + 9;

ll binexp(ll b, ll e)
{
    if(e == 0)  return 1;
    if(e&1) return (b * binexp(b, e-1)) % MOD;
    else
    {
        ll aux = binexp(b, e/2);
        return (aux*aux) % MOD;
    }
}

int countReplacement(int N, int inputSeq[])
{
    if(!valid(N, inputSeq))
        return 0;
    cerr << "valid\n";
    
    int one = -1;
    for(int i = 0; i < N; i++)
        if(input[i] <= N)
            one = (i - input[i] + 1 + N) % N;
    
    vpi seq;
    for(int i = 0; i < N; i++)
        seq.pb({input[(max(one, 0) + i) % N], i + 1});
    sort(all(seq));
    
    int last = N;
    ll ans = 1;
    for(int i = 0; i < N; i++)
    {
        if(seq[i].first <= N)
            continue;
        cerr << seq[i].first << " " << last << "\n";
        ans *= binexp(N - i, seq[i].first - last - 1);
        cerr << ans << "\n";
        last = seq[i].first;
        ans %= MOD;
    }
    if(one < 0)
        ans = (ans * N) % MOD;
    return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 14 ms 2220 KB Output is correct
7 Correct 18 ms 1456 KB Output is correct
8 Correct 22 ms 3928 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 24 ms 4472 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 14 ms 2220 KB Output is correct
7 Correct 18 ms 1276 KB Output is correct
8 Correct 22 ms 3928 KB Output is correct
9 Correct 10 ms 1408 KB Output is correct
10 Correct 24 ms 4440 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 5 ms 384 KB Output is correct
13 Correct 15 ms 2092 KB Output is correct
14 Correct 5 ms 256 KB Output is correct
15 Correct 30 ms 4568 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 20 ms 2168 KB Output is correct
12 Correct 23 ms 2168 KB Output is correct
13 Correct 21 ms 1512 KB Output is correct
14 Correct 20 ms 2040 KB Output is correct
15 Correct 25 ms 2296 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 706 ms 7244 KB Output is correct
10 Correct 514 ms 6208 KB Output is correct
11 Correct 291 ms 2548 KB Output is correct
12 Correct 316 ms 3112 KB Output is correct
13 Correct 80 ms 1024 KB Output is correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 4 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 679 ms 7240 KB Output is correct
10 Correct 511 ms 6148 KB Output is correct
11 Correct 261 ms 2676 KB Output is correct
12 Correct 315 ms 3240 KB Output is correct
13 Correct 86 ms 1120 KB Output is correct
14 Correct 966 ms 9240 KB Output is correct
15 Execution timed out 1096 ms 10188 KB Time limit exceeded
16 Halted 0 ms 0 KB -