iPrva ideja koja mi pada na pamet: jednostruko povezane liste. Trebalo bi da radi u vremenskom ogranicenju. Posto je ideja komplikovana za objasniti, oni koji su voljni da pomognu najlakse ce se snaci u kodu.
#include <iostream>
#include <list>
using namespace std;
#define TYPE unsigned int
list<TYPE> ls,pos;
TYPE i,j,n;
TYPE req,spot,val,lsend(0);
list<TYPE>::iterator it;
list<TYPE>::iterator pit;
int main() {
cin >> n;
for (i=0;i<n;i++) {
scanf("%ld%ld",&req,&spot);
if (req == 1) scanf("%ld",&val);
if (ls.empty()) {
ls.insert(ls.begin(),val); lsend++;
pos.insert(pos.begin(),spot);
continue;
}
it = ls.begin();
pit = pos.begin();
if (req == 1) {
for (j=0;*pit + j <= spot && j < lsend;j++)
{ it++; pit++; }
ls.insert(it,val); lsend++;
pos.insert(pit,spot);
}
if (req == 2) {
val = *it;
for (j=0;*pit + j <= spot && j < lsend;j++) {
val = min( val, *it );
it++; pit++;
}
printf("%ld\n",val);
}
}
system("pause");
}
Nisam pomenuo gresku: tri testa prolaze, a za ostale je WR. Vremensko ogranicenje nije problem...
Jedna greska je bila u ovom delu:
.
.
.
it = ls.begin();
pit = pos.begin();
if (req == 1) {
for (j=0;*pit + j <= spot && j < lsend;j++)
{ it++; pit++; }
ls.insert(it,val); lsend++;
pos.insert(pit,spot);
}
.
.
.
U for petlji uslov treba da bude *pit + j < spot a ne *pit + j <= spot
Ipak, jos ne prolaze svi testovi... =(
Hm... Jedna ideja: sta je tacan izlaz za ovaj test:
3
1 20 101
1 26 70
2 15
U zadatku pise da se u pocetku na svakom polju nalazi neka eskonacno velika vrednost. U ovom slucaju, program bi trebao da ispise tu beskonacno veliku vrednost, ali kolika je ona? 2*10^9? (to je ogranicenje za V)
Za ovo poslednje pitanje: verovatno su primeri napravljeni tako da ovih slucajeva nema.
A nasao sam jos jednu gresku sto se primenjenog algoritma tice. Kod ubacivanja novog broja kada se ubacuje pozicija novog elementa u pomocnu listu POS, vrednost koja se treba ubaciti treba umanjiti za broj elemenata koji se nalaze pre trenutne pozicije.
...
if (req == 1) {
for (j=0;*pit + j <= spot && j < lsend;j++)
{ it++; pit++; }
ls.insert(it,val); lsend++;
pos.insert(pit,spot);
}
...
treba prepraviti u:
if (req == 1) {
for (j=0;*pit + j <= spot && j < lsend;j++)
{ it++; pit++; }
ls.insert(it,val); lsend++;
pos.insert(pit,spot - j);
}
Sada svi testovi osim poslednja tri prolaze. Sada je vreme problem... :(
Ima li iko savet kako ubrzati?
a cekaj zar ne mislis da je lakse da objasnis ideju nego da se neko snalazi u tvom kodu?
dobro, zavisi kome je lakse;)
Evo pokusaja:
Posto je broj pozicija na traci poprilicno veliki ( <= 100000 ) treba smisliti nacin da se e prolazi kroz sve elemente pri dodavanju i nalazenju minimuma, vec samo kroz one koji su dodani. Dakle, imam dve liste LS i POS. LS sadrzi vrednosti elemenata koji su dodani, a POS odgovarajuce pozicije na kojima se nalaze elementi iz liste LS.
Na pocetku imam prazne liste i tokom ubacivanja vodim racuna da popunjavam listu POS kao u insertion sort-u. Dakle, krenem od pocetka liste i prelazim na sledeci element sve dok je zbir pozicije trenutnog elementa i rednog broja elementa u listi manji od pozicije na koji treba ubaciti novi element. Na prvo mesto na kojem nije zadovoljen taj uslov ubacujem novi element.
Kod zahteva tipa 2 je ista stvar (isti uslov) samo sto pri prolasku kroz sve elemente nalazim minimum od svih vrednosti liste LS.
Ima li neko pojma sta pokusavam da objasnim?
Ocigledno da ne... :(
Ok moze li onda predlog nekog pametnijeg resenja?
