oj.uz

Submission #705839

# Submission time Handle Problem Language Result Execution time Memory
705839 2023-03-05T13:11:36 Z penguin133 Gondola (IOI14_gondola) C++17
100 / 100
 20 ms 2732 KB 
#include <bits/stdc++.h>
using namespace std;
#include "gondola.h"
//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
 
int valid(int n, int inputSeq[])
{
  for(int i=1;i<n;i++){
	  if(inputSeq[i] - inputSeq[i-1] != 1 && (inputSeq[i-1] != n || inputSeq[i] != 1))return 0;
  }
  return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  vector <pi> stuf;
  int rot = 0;
  for(int i=0;i<n;i++){
	  if(gondolaSeq[i] <= n)rot = gondolaSeq[i] - i - 1;
  }
  if(rot < 0)rot += n;
  for(int i=0;i<n;i++){
	  if(gondolaSeq[i] > n){
		  int tmp = i + rot + 1;
		  if(tmp > n)tmp -= n;
		  stuf.push_back({gondolaSeq[i], tmp});
	  }
  }
  sort(stuf.begin(), stuf.end());
  int prv = n;
  int in = 0;
  for(auto [i, j] : stuf){
	  replacementSeq[in++] = j;
	  prv++;
	  for(int x = prv + 1; x <= i; x++)replacementSeq[in++] = x - 1;
	  prv = i;
  }
  return in;
}
 
//----------------------
 
const long long mod = (int)1e9 + 9;
 
long long expo(long long a, long long b){
	long long ans = 1LL;
	while(b){
		if(b&1ll)ans *= a, ans %= mod;
		a *= a, a %= mod;
		b >>= 1LL;
	}
	return ans;
}
 
int countReplacement(int n, int inputSeq[])
{
  vector <long long> stuf;
  int rot = -1;
  for(int i=0;i<n;i++){
	  if(inputSeq[i] <= n){
		  int tmp = inputSeq[i] - i - 1;
		  if(tmp < 0)tmp += n;
		  if(rot == -1)rot = tmp;
		  else if(rot != tmp)return 0;
	  }
  }
  for(int i=0;i<n;i++){
	  if(inputSeq[i] > n)stuf.push_back(inputSeq[i]);
  }
  sort(stuf.begin(), stuf.end());
  long long ans = 1, cur = n;
  if(rot == -1)ans = n;
  for(int i=1;i<(int)stuf.size();i++)if(stuf[i] == stuf[i-1])return 0;
  for(int i=0;i<(int)stuf.size();i++){
	  ans *= expo((int)stuf.size() - i, stuf[i] - cur - 1);
	  ans %= mod;
	  cur = stuf[i];
  }
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 312 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 0 ms 316 KB Output is correct
4 Correct 1 ms 316 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 596 KB Output is correct
7 Correct 8 ms 852 KB Output is correct
8 Correct 6 ms 840 KB Output is correct
9 Correct 3 ms 456 KB Output is correct
10 Correct 8 ms 852 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 3 ms 600 KB Output is correct
7 Correct 8 ms 852 KB Output is correct
8 Correct 6 ms 724 KB Output is correct
9 Correct 3 ms 468 KB Output is correct
10 Correct 8 ms 868 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 5 ms 576 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 8 ms 852 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 312 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 2 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 7 ms 808 KB Output is correct
12 Correct 9 ms 888 KB Output is correct
13 Correct 12 ms 1400 KB Output is correct
14 Correct 10 ms 816 KB Output is correct
15 Correct 20 ms 2296 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 308 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 16 ms 1616 KB Output is correct
10 Correct 14 ms 1512 KB Output is correct
11 Correct 5 ms 912 KB Output is correct
12 Correct 6 ms 980 KB Output is correct
13 Correct 2 ms 468 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 13 ms 1608 KB Output is correct
10 Correct 12 ms 1564 KB Output is correct
11 Correct 6 ms 852 KB Output is correct
12 Correct 5 ms 940 KB Output is correct
13 Correct 2 ms 468 KB Output is correct
14 Correct 17 ms 2600 KB Output is correct
15 Correct 18 ms 2732 KB Output is correct
16 Correct 4 ms 940 KB Output is correct
17 Correct 13 ms 1792 KB Output is correct
18 Correct 9 ms 1360 KB Output is correct