oj.uz

Submission #579915

# Submission time Handle Problem Language Result Execution time Memory
579915 2022-06-20T09:00:57 Z 1ne Gondola (IOI14_gondola) C++14
100 / 100
 126 ms 15264 KB 
#include<bits/stdc++.h>
using namespace std;
#include "gondola.h"

int valid(int n, int inputSeq[])
{
	int index = -1;
  for (int i = 0;i<n;++i){
	if (inputSeq[i] <=n){
		index = i;
	}
  }
  map<int,int>visited;
  if (index == -1){
	for (int i = 0;i<n;++i){
		int x = inputSeq[i];
		if (visited[x])return 0;
		visited[x] = true;
	}
	return 1;
  }
  for (int i = 0;i<n;++i){
	int j = (i + index)%n;
	int temp = inputSeq[index] + i;
	if (temp > n)temp = temp % n;
	if (visited[temp] || visited[inputSeq[j]])return 0;
	visited[temp] = true;
	visited[inputSeq[j]] = true;
  }
  return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int index = -1;
  	int maxxy = 1;
  for (int i = 0;i<n;++i){
	if (gondolaSeq[i] <=n){
		index = i;
	}
	maxxy = max(gondolaSeq[i],maxxy);
  }
  map<int,int>visited;
  int init = 1;
  if (index == -1){
	  index = 0;
  }
  else init = gondolaSeq[index];
  int extra = n + 1;
  for (int i = 0;i<n;++i){
	visited[gondolaSeq[i]] = i + 1;
  }
  int cur = 0;
  for (int i = 0;i<n;){
	int j = (i + index)%n;
	int temp = init + i;
	if (temp > n)temp = temp % n;
	if (gondolaSeq[j] == temp){
		++i;
		continue;
	}
	if (gondolaSeq[j] < extra){
		++i;
		continue;
	}
	vector<int>pos;
	while(!visited[extra]){
		pos.push_back(extra);
		extra++;
	}
	if (visited[extra] && extra!=gondolaSeq[j]){
		int temp2 = visited[extra] - index - 1;
		if (temp2 <= 0)temp2+=n;
		temp2 = init + temp2;
		if (temp2 > n)temp2 = temp2 % n;
		replacementSeq[cur++] = temp2;
		for (auto x:pos){
			replacementSeq[cur++] = x;
		}
		extra++;
	}
	else{
		replacementSeq[cur++] = temp;
		for (auto x:pos){
			replacementSeq[cur++] = x;
		}
		extra++;
		++i;
	}
  }
  return cur;
}

//----------------------
int countReplacement(int n, int inputSeq[])
{
	if (!valid(n,inputSeq))return 0;
	int index = -1;
  for (int i = 0;i<n;++i){
	if (inputSeq[i] <=n){
		index = i;
	}
  }
  map<int,int>visited;
  const int mod = 1e9 + 9;
  long long ans = 1;
  int init = 1;
  bool ok = false;
  if (index == -1){
	  ok = true;
	  index = 0;
  }
  for (int i = 0;i<n;++i){
	visited[inputSeq[i]] = i + 1;
  }
  int extra = n + 1;
  vector<int>gondola;
  for (int i = 0;i<n;++i)gondola.push_back(inputSeq[i]);
  sort(gondola.begin(),gondola.end());
  int time = 0;
  vector<long long>arr(4 * n,0),pref(4 * n + 1,0);
  vector<pair<long long,long long>>brr;
  for (int i = 0;i<n;){
	time++;
	int j = (i + index)%n;
	int temp = init + i;
	if (temp > n)temp = temp % n;
	if (inputSeq[j] == temp){
		++i;
		continue;
	}
	if (inputSeq[j] < extra){
		++i;
		continue;
	}
	long long counts = 0;
	if(!visited[extra]){
		int p = upper_bound(gondola.begin(),gondola.end(),extra) - gondola.begin();
		counts = gondola[p] - extra;
		extra = gondola[p];
		brr.push_back({time,counts});
	}
	if (visited[extra] && extra!=inputSeq[j]){
		int temp2 = visited[extra] - index - 1;
		if (temp2 <= 0)temp2+=n;
		temp2 = init + temp2;
		if (temp2 > n)temp2 = temp2 % n;
		arr[time]++;
		extra++;
	}
	else{
		arr[time]++;
		extra++;
		++i;
	}
  }
  assert(time < 4 * n);
  for (int i = 0;i<4 * n;++i){
	pref[i + 1] = (pref[i] + arr[i])%mod;
  }
  auto power = [&](long long a,long long b){
	  long long res = 1;
	  while(b){
		if (b & 1){
			res = (res * a)%mod;
		}
		a = (a * a)%mod;
		b>>=1;
	  }
	  return res;  
  };
  for (auto x:brr){
	long long temp = pref[4 * n] - pref[x.first];
	//cout<<temp<<" "<<x.second<<'\n';
	ans = (ans * power(temp,x.second))%mod;
  }
  if (ok)ans = (ans * n)%mod;
  return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 232 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 18 ms 2124 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 32 ms 3836 KB Output is correct
9 Correct 10 ms 1364 KB Output is correct
10 Correct 48 ms 4428 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 21 ms 2132 KB Output is correct
7 Correct 8 ms 596 KB Output is correct
8 Correct 33 ms 3864 KB Output is correct
9 Correct 10 ms 1364 KB Output is correct
10 Correct 44 ms 4440 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 6 ms 896 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 9 ms 596 KB Output is correct

Subtask #4
5.0 / 5.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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 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 212 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 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 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 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 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 340 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 2 ms 468 KB Output is correct
11 Correct 20 ms 4308 KB Output is correct
12 Correct 23 ms 4820 KB Output is correct
13 Correct 33 ms 4692 KB Output is correct
14 Correct 26 ms 4156 KB Output is correct
15 Correct 56 ms 9940 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 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 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 1 ms 308 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 0 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 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 113 ms 12812 KB Output is correct
10 Correct 76 ms 10148 KB Output is correct
11 Correct 37 ms 4484 KB Output is correct
12 Correct 37 ms 5292 KB Output is correct
13 Correct 6 ms 1364 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 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 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 107 ms 12908 KB Output is correct
10 Correct 84 ms 10140 KB Output is correct
11 Correct 33 ms 4452 KB Output is correct
12 Correct 40 ms 5324 KB Output is correct
13 Correct 6 ms 1364 KB Output is correct
14 Correct 126 ms 13528 KB Output is correct
15 Correct 123 ms 15264 KB Output is correct
16 Correct 19 ms 3112 KB Output is correct
17 Correct 73 ms 10392 KB Output is correct
18 Correct 47 ms 6084 KB Output is correct