oj.uz

Submission #363548

# Submission time Handle Problem Language Result Execution time Memory
363548 2021-02-06T14:21:26 Z silverfish Gondola (IOI14_gondola) C++14
55 / 100
 48 ms 4736 KB 
#include <bits/stdc++.h>
#include "gondola.h"

using namespace std;
#define ar array
#define pb push_back

int valid(int n, int a[]){
	bool ok = 1, first = 1;
	int diff = -1;
	map<int, int> cnt;
	for(int i = 0; i < n; ++i){
		if(cnt[a[i]]) ok = 0;
		++cnt[a[i]];
		if(a[i] <= n){
			if(first) {
				diff = (a[i]-(i+1)+n)%n;
				first = 0;
				continue;
			}
			//cerr << i+1 << ' ' << (n+a[i]-diff)%n << endl;
			if(i != (a[i]-diff-1+n)%n) ok = 0;
		}
	}

	return ok;
}

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

int replacement(int n, int a[], int r[]){
	bool ok = 1, first = 1;
	int diff = -1;
	vector<ar<int,2>> replaced;

	for(int i = 0; i < n; ++i){
		if(a[i] <= n){
			diff = (a[i]-(i+1)+n)%n;
		}else{
			replaced.pb({a[i], i});
		}
	}
	if(diff == -1) diff = 0;
	sort(replaced.begin(), replaced.end());
	int cur = 0, curnum = n;

	for(auto x : replaced){
		int orig = (x[1]+1+diff);
		if(orig > n) orig -= n;
		r[cur++] = orig;
		++curnum;
		for(; curnum < x[0]; ++curnum) r[cur++] = curnum;
	}
	return cur;
}

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

int countReplacement(int n, int a[]){
	if(!valid(n, a)) return 0;

	return -1;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:32:7: warning: unused variable 'ok' [-Wunused-variable]
   32 |  bool ok = 1, first = 1;
      |       ^~
gondola.cpp:32:15: warning: unused variable 'first' [-Wunused-variable]
   32 |  bool ok = 1, first = 1;
      |               ^~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 2284 KB Output is correct
7 Correct 45 ms 3692 KB Output is correct
8 Correct 39 ms 3948 KB Output is correct
9 Correct 9 ms 1516 KB Output is correct
10 Correct 34 ms 4588 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 2284 KB Output is correct
7 Correct 40 ms 3748 KB Output is correct
8 Correct 31 ms 3948 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 34 ms 4588 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 0 ms 364 KB Output is correct
13 Correct 19 ms 2156 KB Output is correct
14 Correct 1 ms 512 KB Output is correct
15 Correct 48 ms 4736 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 10 ms 1132 KB Output is correct
12 Correct 11 ms 1152 KB Output is correct
13 Correct 17 ms 1532 KB Output is correct
14 Correct 10 ms 1132 KB Output is correct
15 Correct 25 ms 2404 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Integer -1 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB Integer -1 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 KB Integer -1 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 364 KB Integer -1 violates the range [0, 1000000008]
2 Halted 0 ms 0 KB -