답안 #999222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999222	2024-06-15T08:21:08 Z	Alfraganus	곤돌라 (IOI14_gondola)	C++17	75 / 100	33 ms	4576 KB

gondola

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

int valid(int n, int a[]){
  vector<int> p;
  for(int i = 0; i < n; i ++){
    if(a[i] == 1){
      for(int j = i; j < n; j ++)
        p.push_back(a[j]);
      for(int j = 0; j < i; j ++)
        p.push_back(a[j]);
    }
  }
  if(p.size() == 0)
    return 0;
  for(int i = 0; i < n; i ++){
    if(p[i] != i + 1){
      return 0;
    }
  }
  return 1;
}

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

int replacement(int n, int a[], int replacementSeq[])
{
  int index = 0;
  for(int i = 0; i < n; i ++){
    if(a[i] <= n){
      index = (i - a[i] + 1 + n) % n;
      break;
    }
  }
  map<int, int> mp;
  int mx = 0;
  for(int i = index; i < n; i ++)
    if(a[i] > n)
      mp[a[i]] = i - index + 1, mx = max(mx, a[i]);
  for(int i = 0; i < index; i ++)
    if(a[i] > n)
      mp[a[i]] = i + n - index + 1, mx = max(mx, a[i]);
  if(mp.size() == 0)
    return 0;
  int ans = 0;
  for(int i = n + 1; i <= mx; i ++){
    if(mp.begin() -> first == i){
      replacementSeq[ans] = mp[i];
      mp.erase(mp.begin());
      ans ++;
    }
    else{
      replacementSeq[ans] = mp.begin() -> second;
      mp.begin() -> second = i;
      ans ++;
    }
  }
  return ans;
}

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

int countReplacement(int n, int a[]){
  map<int, int> cnt;
  for(int i = 0; i < n; i ++){
    cnt[a[i]] ++;
    if(cnt[a[i]] == 2)
      return 0;
  }
  int index = 0;
  for(int i = 0; i < n; i ++){
    if(a[i] <= n){
      index = (i - a[i] + 1 + n) % n;
      break;
    }
  }
  for(int i = index; i < n; i ++){
    if(a[i] <= n and a[i] != i - index + 1){
      return 0;
    }
  }
  for(int i = 0; i < index; i ++){
    if(a[i] <= n and a[i] != i + n - index + 1){
      return 0;
    }
  }
  long long ans = 1, mod = 1e9 + 9;
  vector<int> p;
  for(int i = 0; i < n; i ++)
    if(a[i] > n)
      p.push_back(a[i]);
  sort(p.begin(), p.end(), greater<int> ());
  auto binpow = [&](long long a, int n){
    long long res = 1;
    while(n){
      if(n & 1)
        res = (res * a) % mod;
      a = (a * a) % mod;
      n >>= 1;
    }
    return res;
  };
  long long x = (int)p.size();
  for(int i = (int)p.size() - 1; i >= 0; i --){
    ans = (ans * binpow(x, p[i] - (i + 1 == (int)p.size() ? n : p[i + 1]) - 1)) % mod;
    x --;
  }
  int res = ans;
  return res;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	348 KB	Output is correct
2	Correct	348 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	344 KB	Output is correct
5	Correct	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	3 ms	980 KB	Output is correct
7	Correct	6 ms	1240 KB	Output is correct
8	Correct	5 ms	1240 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	5 ms	1300 KB	Output is correct

Subtask #3
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	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	2 ms	860 KB	Output is correct
7	Correct	7 ms	1240 KB	Output is correct
8	Correct	5 ms	1240 KB	Output is correct
9	Correct	2 ms	604 KB	Output is correct
10	Correct	7 ms	1236 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	3 ms	412 KB	Output is correct
14	Correct	0 ms	344 KB	Output is correct
15	Correct	6 ms	1240 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	348 KB	Output is correct
3	Correct	0 ms	356 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct

Subtask #5
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	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	344 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	360 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	416 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	464 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	5 ms	604 KB	Output is correct
12	Correct	6 ms	604 KB	Output is correct
13	Correct	14 ms	2488 KB	Output is correct
14	Correct	5 ms	604 KB	Output is correct
15	Correct	15 ms	2940 KB	Output is correct

Subtask #7
5.0 / 5.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

Subtask #8
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	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

Subtask #9
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	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	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	32 ms	4576 KB	Output is correct
10	Correct	25 ms	3736 KB	Output is correct
11	Correct	9 ms	1628 KB	Output is correct
12	Correct	12 ms	2004 KB	Output is correct
13	Incorrect	4 ms	604 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Subtask #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	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	0 ms	348 KB	Output is correct
9	Correct	33 ms	4444 KB	Output is correct
10	Correct	25 ms	3928 KB	Output is correct
11	Correct	10 ms	1624 KB	Output is correct
12	Correct	11 ms	1820 KB	Output is correct
13	Incorrect	2 ms	604 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

답안 #999222

Compilation message