oj.uz

Submission #72903

# Submission time Handle Problem Language Result Execution time Memory
72903 2018-08-27T08:08:43 Z nvmdava Gondola (IOI14_gondola) C++17
20 / 100
 69 ms 5168 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
 
struct Gondola{
	int id, val;
	Gondola(int _id, int _val){
		id = _id;
		val = _val;
	}
	bool operator<(const Gondola& rhs) const{
		val < rhs.val;
	}
};
 
int ord[100001];
map<int, int> in;
vector<Gondola> v;
 
 
int valid(int n, int inputSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(in[inputSeq[i]]) return 0;
		in[inputSeq[i]] = 1;
	}
	for(i = 0; i < n; i++){
		if(inputSeq[i] <= n) break;
	}
	if(i == n) return 1;
	int k = inputSeq[i] - 1;
	for(int j = 0; j < n; j++){
		ord[(k + j) % n] = inputSeq[(i + j) % n];
		if((ord[(k + j) % n] != (k + j) % n + 1 && ord[(k + j) % n] <= n) || ord[(k + j) % n] < 1) return 0;
	}
	for(i = 0; i < n; i++){
		if((ord[i] != i + 1 && ord[i] <= n) || ord[i] < 1) return 0;
	}
	return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(gondolaSeq[i] <= n) break;
	}
	int k;
	if(i == n){
		i = 0;
		k = 0;
	} else {
		k = gondolaSeq[i] - 1;	
	}
	for(int j = 0; j < n; j++){
		v.push_back(Gondola((k + j) % n + 1, ord[(k + j) % n]));
	}
	sort(v.begin(), v.end());
	i = 0;
	int s = n + 1;
	for(auto x : v){
		if(x.val <= n) continue;
		replacementSeq[i] = x.id;
		i++;
		for(; s < x.val; s++){
			replacementSeq[i] = s;
			i++;
		}
		s = x.val + 1;
	}
	return i;
}
 
//----------------------
 
int countReplacement(int n, int inputSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(inputSeq[i] <= n) break;
	}
	int k;
	if(i == n){
		i = 0;
		k = 0;
	} else {
		k = inputSeq[i] - 1;	
	}
	for(int j = 0; j < n; j++){
		ord[(k + j) % n] = inputSeq[(i + j) % n];
	}
}

Compilation message

gondola.cpp: In member function 'bool Gondola::operator<(const Gondola&) const':
gondola.cpp:12:7: warning: statement has no effect [-Wunused-value]
   val < rhs.val;
   ~~~~^~~~~~~~~
gondola.cpp:13:2: warning: no return statement in function returning non-void [-Wreturn-type]
  }
  ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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 488 KB Output is correct
3 Correct 3 ms 524 KB Output is correct
4 Correct 2 ms 524 KB Output is correct
5 Correct 2 ms 524 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 524 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 2 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Correct 22 ms 2640 KB Output is correct
7 Correct 16 ms 2640 KB Output is correct
8 Correct 38 ms 4432 KB Output is correct
9 Correct 14 ms 4432 KB Output is correct
10 Correct 50 ms 5120 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5120 KB Output is correct
2 Correct 3 ms 5120 KB Output is correct
3 Correct 3 ms 5120 KB Output is correct
4 Correct 2 ms 5120 KB Output is correct
5 Correct 2 ms 5120 KB Output is correct
6 Correct 21 ms 5120 KB Output is correct
7 Correct 14 ms 5120 KB Output is correct
8 Correct 37 ms 5120 KB Output is correct
9 Correct 13 ms 5120 KB Output is correct
10 Correct 49 ms 5168 KB Output is correct
11 Correct 3 ms 5168 KB Output is correct
12 Correct 2 ms 5168 KB Output is correct
13 Correct 29 ms 5168 KB Output is correct
14 Correct 2 ms 5168 KB Output is correct
15 Correct 69 ms 5168 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 5168 KB Output isn't correct
2 Halted 0 ms 0 KB -