oj.uz

Submission #91168

# Submission time Handle Problem Language Result Execution time Memory
91168 2018-12-26T12:39:45 Z arman_ferdous Gondola (IOI14_gondola) C++17
55 / 100
 47 ms 5412 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

set<int> st;
int valid(int n, int inputSeq[]) {
	int last = -1, start = -1, num = 1000000;
	for(int i = 0; i < n; i++) {
		st.insert(inputSeq[i]);
		if(inputSeq[i] > n) inputSeq[i] = -1;
		else {
			last = i;
			if(inputSeq[i] < num) 
				start = i, num = inputSeq[i];
		}
	}
	if(st.size() != n) return 0;
	if(last == -1) return 1;
	for(int i = start; i < n; i++)
		if(inputSeq[i] + 1 && inputSeq[i] != num + i - start)
			return 0;
	int at0 = inputSeq[last] + n - last;
	for(int i = 0; i < start; i++)
		if(inputSeq[i] + 1 && inputSeq[i] != at0 + i)
			return 0;

  	return 1;
}

int init[100001];
vector< pair<int,int> > v;
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int start = -1;
 	for(int i = 0; i < n; i++) if(gondolaSeq[i] <= n) {
		start = i - gondolaSeq[i] + 1;
		if(start < 0) start += n;
		break;
	} if(start == -1) start = 0;
	int cur = 1;
 	for(int i = start; i < n; i++) init[i] = cur++;
 	for(int i = 0; i < start; i++) init[i] = cur++;

 	for(int i = 0; i < n; i++) if(gondolaSeq[i] > n)
 		v.push_back({gondolaSeq[i], i});
 	sort(v.begin(), v.end());

 	int ptr = 0;
 	for(auto it : v) {
 		while(cur <= it.first) {
 			replacementSeq[ptr++] = init[it.second];
 			init[it.second] = cur;
 			cur++;
 		}
 	} return ptr;
}

int countReplacement(int n, int inputSeq[])
{
 	return -3;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(st.size() != n) return 0;
     ~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 464 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 2 ms 516 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 536 KB Output is correct
2 Correct 2 ms 540 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 596 KB Output is correct
6 Correct 12 ms 2648 KB Output is correct
7 Correct 30 ms 4080 KB Output is correct
8 Correct 22 ms 4352 KB Output is correct
9 Correct 8 ms 4352 KB Output is correct
10 Correct 29 ms 4992 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4992 KB Output is correct
2 Correct 2 ms 4992 KB Output is correct
3 Correct 2 ms 4992 KB Output is correct
4 Correct 2 ms 4992 KB Output is correct
5 Correct 2 ms 4992 KB Output is correct
6 Correct 13 ms 4992 KB Output is correct
7 Correct 30 ms 4992 KB Output is correct
8 Correct 24 ms 4992 KB Output is correct
9 Correct 8 ms 4992 KB Output is correct
10 Correct 29 ms 5036 KB Output is correct
11 Correct 2 ms 5036 KB Output is correct
12 Correct 2 ms 5036 KB Output is correct
13 Correct 17 ms 5036 KB Output is correct
14 Correct 2 ms 5036 KB Output is correct
15 Correct 47 ms 5412 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5412 KB Output is correct
2 Correct 1 ms 5412 KB Output is correct
3 Correct 2 ms 5412 KB Output is correct
4 Correct 2 ms 5412 KB Output is correct
5 Correct 2 ms 5412 KB Output is correct
6 Correct 2 ms 5412 KB Output is correct
7 Correct 2 ms 5412 KB Output is correct
8 Correct 2 ms 5412 KB Output is correct
9 Correct 2 ms 5412 KB Output is correct
10 Correct 2 ms 5412 KB Output is correct
11 Correct 10 ms 5412 KB Output is correct
12 Correct 11 ms 5412 KB Output is correct
13 Correct 14 ms 5412 KB Output is correct
14 Correct 10 ms 5412 KB Output is correct
15 Correct 18 ms 5412 KB Output is correct

Subtask #7
0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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