oj.uz

답안 #960177

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
960177 2024-04-09T19:56:07 Z Nelt 곤돌라 (IOI14_gondola) C++17
100 / 100
 38 ms 6744 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define ll long long
#define endl "\n"

using namespace std;
const ll mod = 1e9 + 9;
ll binpow(ll n, ll p)
{
    ll ans = 1;
    n %= mod;
    while (p)
    {
        ans = (p & 1 ? ans * n % mod : ans);
        p >>= 1;
        n = n * n % mod;
    }
    return ans;
}
int valid(int n, int a[])
{
    set<ll> s;
    for (ll i = 0; i < n; i++)
        s.insert(a[i]);
    if (s.size() != n)
        return 0;
    ll st = -1, b[n];
    for (ll i = 0; i < n; i++)
        if (a[i] <= n)
            st = i;
    if (st == -1)
        return 1;
    b[st] = a[st];
    for (ll i = st + 1; i < st + n; i++)
        b[i % n] = b[(i - 1 + n) % n] % n + 1;
    // for (ll i = 0; i < n; i++)
    //     cout << b[i] << " ";
    // cout << endl;
    for (ll i = 0; i < n; i++)
        if (a[i] <= n and a[i] != b[i])
            return 0;
    return 1;
}

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

int replacement(int n, int a[], int replacementSeq[])
{
    ll st = -1, b[n];
    for (ll i = 0; i < n; i++)
        if (a[i] <= n)
            st = i;
    if (st == -1)
        iota(b, b + n, 1);
    else
    {
        b[st] = a[st];
        for (ll i = st + 1; i < st + n; i++)
            b[i % n] = b[(i - 1 + n) % n] % n + 1;
    }
    ll ptr = 0, mx = max_element(a, a + n) - a;
    ll ind[a[mx] + 1];
    for (ll i = 0; i <= a[mx]; i++)
        ind[i] = -1;
    for (ll i = 0; i < n; i++)
        ind[a[i]] = i;
    for (ll i = n + 1; i <= a[mx]; i++)
        if (ind[i] != -1)
            replacementSeq[ptr++] = b[ind[i]], b[ind[i]] = i;
        else
            replacementSeq[ptr++] = b[mx], b[mx] = i;
    return ptr;
}

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

int countReplacement(int n, int a[])
{
    if (!valid(n, a))
        return 0;
    ll ans = 1;
    ll b[n];
    for (ll i = 0; i < n; i++)
        b[i] = a[i];
    sort(b, b + n, greater());
    for (ll i = 0; i < n and b[i] > n; i++)
        ans = ans * binpow(i + 1, b[i] - max((ll)n, i + 1 < n ? b[i + 1] : 1) - 1) % mod;
    if (b[n - 1] > n)
        ans = ans * n % mod;
    return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:26:18: warning: comparison of integer expressions of different signedness: 'std::set<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   26 |     if (s.size() != n)
      |         ~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2396 KB Output is correct
7 Correct 19 ms 3740 KB Output is correct
8 Correct 15 ms 4440 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 19 ms 5212 KB Output is correct

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 8 ms 2496 KB Output is correct
7 Correct 19 ms 3724 KB Output is correct
8 Correct 19 ms 4952 KB Output is correct
9 Correct 5 ms 1628 KB Output is correct
10 Correct 19 ms 5320 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 12 ms 2396 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 25 ms 5468 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 8 ms 1804 KB Output is correct
12 Correct 8 ms 2140 KB Output is correct
13 Correct 11 ms 2396 KB Output is correct
14 Correct 7 ms 1880 KB Output is correct
15 Correct 16 ms 3676 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 27 ms 4952 KB Output is correct
10 Correct 21 ms 4000 KB Output is correct
11 Correct 7 ms 1624 KB Output is correct
12 Correct 9 ms 1884 KB Output is correct
13 Correct 2 ms 604 KB Output is correct

Subtask #10
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 32 ms 4696 KB Output is correct
10 Correct 25 ms 3928 KB Output is correct
11 Correct 7 ms 1628 KB Output is correct
12 Correct 10 ms 2044 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 31 ms 5980 KB Output is correct
15 Correct 38 ms 6744 KB Output is correct
16 Correct 6 ms 1628 KB Output is correct
17 Correct 23 ms 4620 KB Output is correct
18 Correct 13 ms 2716 KB Output is correct