제출 #634262

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634262		l_reho	코끼리 (Dancing Elephants) (IOI11_elephants)	C++14	26 / 100	9092 ms	2752 KiB

elephants

#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 / 10
• Subtask 2: 16 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3