oj.uz

Submission #634262

# Submission time Handle Problem Language Result Execution time Memory
634262 2022-08-24T08:06:40 Z l_reho Dancing Elephants (IOI11_elephants) C++14
26 / 100
 9000 ms 2752 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
set<pair<int, int>> V;
int l = 0;
void init(int N, int L, int X[]){
	n = N;
	l = L;
	
	for(int i = 0; i < N; i++) V.insert({X[i], i});
	
	/*
	
	for(int i = 0; i < N; i++){
		if(prev_pos == -1 || V[i].first > prev_pos+L) camPos[i] = 1, prev_pos = V[i].first;
		posInCamPos[V[i].second] = i;
	}
	build(1, 0, N-1);
	
	*/
	
	
}


// facciamo 26 punti
int update(int i, int y){
	
	// Mi serve la posizione dell'elefante i all'interno di camPos
	
	// quando faccio l'update della posizione, come cambiano le cose?
	// posso fare molte operazioni in O(logN) usando i set
	
	// Cambio la posizione dell'elefante i all'interno di camPos ()
	// prenderà il posto di qualcun'altro
	
	int tot = 0;
	
	for(set<pair<int, int>>::iterator it = V.begin(); it != V.end(); it++){
		if((*it).second == i){
			V.erase(it);
			break;
		}
	}
	
	V.insert({y, i});
	
	
	int prev_pos = -1;
	
	
	for(auto v : V)
		if(prev_pos == -1 || v.first > prev_pos+l) prev_pos = v.first, tot++;
	
	// riassegno le camere nelle vicinanze
	
	// trovo la prima cam, prima di y, trovo la prima cam dopo y, controllo
	// se una delle due interseca y
	// se è così apposto, altrimenti sposto la successiva indietro su y e 
	// vedo se funziona, se non funziona la lascio dove sta e aggiungo una camera
	
	return tot;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7377 ms 2444 KB Output is correct
8 Execution timed out 9092 ms 2752 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7377 ms 2444 KB Output is correct
8 Execution timed out 9092 ms 2752 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 7377 ms 2444 KB Output is correct
8 Execution timed out 9092 ms 2752 KB Time limit exceeded
9 Halted 0 ms 0 KB -