oj.uz

Submission #739301

# Submission time Handle Problem Language Result Execution time Memory
739301 2023-05-10T10:07:23 Z NeroZein Gondola (IOI14_gondola) C++17
60 / 100
 15 ms 1748 KB 
#include "gondola.h"
#include <bits/stdc++.h> 
using namespace std; 
 
const int M = (int) 1e6 + 1;
const int md = (int) 1e9 + 9; 

int n; 
int mx; 
int a[M]; 
int b[M]; 
bitset<M> vis;

bool Go (int id, int cur, int step) {
	if (id < 0 || id >= n) {
		return true; 
	}
	if (cur == 0) cur = n; 
	if (cur == n + 1) cur = 1; 
	b[id] = cur; 
	if (a[id] <= n && a[id] != cur) {
		return false; 
	}
	return Go(id + step, cur + step, step); 
}; 
 
int valid(int n_, int inputSeq[]) {
	n = n_; 
	for (int i = 0; i < n; ++i) {
		a[i] = inputSeq[i]; 
	}
	for (int i = 0; i < n; ++i) {
		if (vis[a[i]] == true) {
			return false; 
		}
		mx = max(mx, a[i]);
		vis[a[i]] = true;
	}
	bool ret = true; 
  for (int i = 0; i < n; ++i) {
		if (inputSeq[i] <= n) {
			ret &= Go(i, a[i], 1);
			vis[inputSeq[i]] = 0;  
			ret &= Go(i, a[i], -1); 
			break; 
		}
	}
	return ret;
}
 
int replacement(int n_, int gondolaSeq[], int replacementSeq[]) {
	n = n_; 
	for (int i = 0; i < n; ++i) {
		a[i] = gondolaSeq[i]; 
	}
	bool f = false; 
	for (int i = 0; i < n; ++i) {
		mx = max(mx, a[i]); 
		vis[a[i]] = true; 
		if (a[i] <= n) {
			f = true; 
		}
	}  
	int ans = 0; 
	if (!f) {
		for (int i = 1; i <= mx; ++i) {
			if (!vis[i]) {
				replacementSeq[ans++] = i;  
			}
		}
		return ans; 		
	}
	for (int i = 0; i < n; ++i) {
		if (gondolaSeq[i] <= n) {
			Go(i, gondolaSeq[i], 1); 
			Go(i, gondolaSeq[i], -1); 
			break; 
		}
	}
	vector<pair<int, int>> ord(n);
	for (int i = 0; i < n; ++i) {
		ord[i] = make_pair(a[i], b[i]); 
	} 
	sort(ord.begin(), ord.end()); 
	for (int p = 0, g = n + 1; p < n; ++p) {
		if (vis[ord[p].second]) {
			assert(ord[p].first == ord[p].second); 
			continue; 
		}
		replacementSeq[ans++] = ord[p].second; 
		while (g < ord[p].first) {
			replacementSeq[ans++] = g++;			
		}
		g++; 
	}
	return ans; 
}
 
//----------------------
 
int countReplacement(int n_, int inputSeq[]) {
	n = n_; 
  if (!valid(n, inputSeq)) {
		return 0; 
	}
	bool f = false; 
	for (int i = 0; i < n; ++i) {
		if (inputSeq[i] <= n) {
			f = true; 
		}
	}
	int ans = 1;
	if (!f) {
		ans = n; 
	}
	int cnt = 0;  
	for (int i = mx; i > n; --i) {
		if (vis[i]) {
			cnt++; 
			continue; 
		}
		ans = (long long) ans * cnt % md; 
	}
	return ans; 
}

Subtask #1
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 0 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 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 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 8 ms 980 KB Output is correct
8 Correct 8 ms 1108 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 8 ms 1308 KB Output is correct

Subtask #3
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 340 KB Output is correct
5 Correct 0 ms 260 KB Output is correct
6 Correct 4 ms 724 KB Output is correct
7 Correct 8 ms 1028 KB Output is correct
8 Correct 7 ms 1176 KB Output is correct
9 Correct 2 ms 596 KB Output is correct
10 Correct 8 ms 1236 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 4 ms 596 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 9 ms 980 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 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
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 0 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 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 340 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 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Incorrect 1 ms 340 KB Output isn't correct
9 Halted 0 ms 0 KB -

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 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 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 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 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 9 ms 1192 KB Output is correct
10 Correct 7 ms 980 KB Output is correct
11 Correct 4 ms 596 KB Output is correct
12 Correct 4 ms 724 KB Output is correct
13 Correct 2 ms 340 KB Output is correct

Subtask #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 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 0 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 9 ms 1196 KB Output is correct
10 Correct 7 ms 980 KB Output is correct
11 Correct 3 ms 596 KB Output is correct
12 Correct 4 ms 628 KB Output is correct
13 Correct 2 ms 340 KB Output is correct
14 Runtime error 15 ms 1748 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -