답안 #920787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
920787	2024-02-03T03:24:55 Z	rxlfd314	곤돌라 (IOI14_gondola)	C++17	80 / 100	39 ms	5212 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

int valid(int N, int *A) {
  map<int, int> cnt;
  FOR(i, 0, N-1)
    if (++cnt[--A[i]] > 1)
      return 0;
  FOR(i, 0, N-1)
    if (A[i] < N) {
      FOR(j, 0, N-1)
        if (A[(i+j)%N] < N && A[(i+j)%N] != (A[i]+j)%N)
          return 0;
      break;
    }
  return 1;
}

int replacement(int N, int *A, int *ans) {
  int start = 0;
  FOR(i, 0, N-1)
    if (A[i]-- < 2)
      start = i;
  vt<int> B(N);
  FOR(i, 0, N-1)
    B[(start+i)%N] = i;
  
  vt<int> ord(N);
  iota(all(ord), 0);
  sort(all(ord), [&](const int &a, const int &b) {
    return A[a] < A[b];    
  });
  
  vt<int> res;
  FOR(ii, 0, N-1) {
    int i = ord[ii];
    if (A[i] < N)
      continue;
    res.push_back(B[i]);
    B[i] = N + size(res) - 1;
    for (; B[i] < A[i]; B[i]++)
      res.push_back(B[i]);
  }
  
  FOR(i, 0, size(res)-1)
    ans[i] = res[i] + 1;
  return size(res);
}

constexpr int MOD = 1e9 + 9;
int binpow(int a, int b) {
  int ret = 1;
  for (; b; b >>= 1, a = 1ll * a * a % MOD)
    if (b & 1)
      ret = 1ll * ret * a % MOD;
  return ret;
}

int countReplacement(int N, int *A) {
  if (!valid(N, A))
    return 0;
  sort(A, A+N);
  int ans = 1;
  FOR(i, 0, N-1)
    if (A[i] >= N) {
      #ifdef DEBUG
      cout << "bruh: " << binpow(N - i, A[i] - (i ? max(N-1, A[i-1])+1 : N)) << ' ' << A[i] << ' ' << A[i-1] << '\n';
      #endif
      ans = 1ll * ans * binpow(N - i, A[i] - (i ? max(N-1, A[i-1])+1 : N)) % MOD;
    }
  return 1ll * ans * (A[0] >= N ? N : 1) % MOD;
}

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	1 ms	348 KB	Output is correct
4	Correct	1 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	1 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	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	8 ms	2140 KB	Output is correct
7	Correct	7 ms	580 KB	Output is correct
8	Correct	15 ms	3932 KB	Output is correct
9	Correct	5 ms	1368 KB	Output is correct
10	Correct	18 ms	4540 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	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	348 KB	Output is correct
6	Correct	8 ms	2136 KB	Output is correct
7	Correct	8 ms	604 KB	Output is correct
8	Correct	23 ms	3932 KB	Output is correct
9	Correct	5 ms	1368 KB	Output is correct
10	Correct	19 ms	4552 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	1 ms	348 KB	Output is correct
13	Correct	11 ms	2396 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	29 ms	5144 KB	Output is correct

Subtask #4
5.0 / 5.0

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

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

Subtask #6
0 / 20.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	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	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 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	10 ms	1492 KB	Output is correct
12	Correct	10 ms	1372 KB	Output is correct
13	Incorrect	16 ms	1496 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

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	0 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	0 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct

Subtask #9
15.0 / 15.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	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	30 ms	4028 KB	Output is correct
10	Correct	23 ms	3420 KB	Output is correct
11	Correct	9 ms	1372 KB	Output is correct
12	Correct	10 ms	1716 KB	Output is correct
13	Correct	3 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	1 ms	348 KB	Output is correct
3	Correct	1 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	0 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	36 ms	3932 KB	Output is correct
10	Correct	22 ms	3420 KB	Output is correct
11	Correct	11 ms	1372 KB	Output is correct
12	Correct	11 ms	1628 KB	Output is correct
13	Correct	4 ms	756 KB	Output is correct
14	Correct	35 ms	4624 KB	Output is correct
15	Correct	39 ms	5212 KB	Output is correct
16	Correct	8 ms	1112 KB	Output is correct
17	Correct	26 ms	3672 KB	Output is correct
18	Correct	14 ms	2136 KB	Output is correct

답안 #920787

Compilation message