| Task: | Maalarit |
| Sender: | kh |
| Submission time: | 2016-10-11 19:44:34 +0300 |
| Language: | Java |
| Status: | READY |
| Result: | 12 |
| group | verdict | score |
|---|---|---|
| #1 | ACCEPTED | 12 |
| #2 | WRONG ANSWER | 0 |
| #3 | WRONG ANSWER | 0 |
| #4 | TIME LIMIT EXCEEDED | 0 |
| test | verdict | time | group | |
|---|---|---|---|---|
| #1 | ACCEPTED | 0.24 s | 1 | details |
| #2 | ACCEPTED | 0.24 s | 1 | details |
| #3 | ACCEPTED | 0.24 s | 1 | details |
| #4 | ACCEPTED | 0.23 s | 1 | details |
| #5 | ACCEPTED | 0.23 s | 1 | details |
| #6 | ACCEPTED | 0.24 s | 1 | details |
| #7 | ACCEPTED | 0.28 s | 2 | details |
| #8 | ACCEPTED | 0.32 s | 2 | details |
| #9 | ACCEPTED | 0.28 s | 2 | details |
| #10 | ACCEPTED | 0.26 s | 2 | details |
| #11 | WRONG ANSWER | 0.31 s | 2 | details |
| #12 | ACCEPTED | 0.24 s | 2 | details |
| #13 | WRONG ANSWER | 0.28 s | 3 | details |
| #14 | ACCEPTED | 0.28 s | 3 | details |
| #15 | ACCEPTED | 0.25 s | 3 | details |
| #16 | WRONG ANSWER | 0.33 s | 3 | details |
| #17 | WRONG ANSWER | 0.29 s | 3 | details |
| #18 | ACCEPTED | 0.23 s | 3 | details |
| #19 | TIME LIMIT EXCEEDED | -- | 4 | details |
| #20 | TIME LIMIT EXCEEDED | -- | 4 | details |
| #21 | TIME LIMIT EXCEEDED | -- | 4 | details |
| #22 | TIME LIMIT EXCEEDED | -- | 4 | details |
| #23 | TIME LIMIT EXCEEDED | -- | 4 | details |
| #24 | ACCEPTED | 1.34 s | 4 | details |
Code
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;
public class Maalarit2 {
public static void main(String[] args) {
Scanner lukija = new Scanner(System.in);
HashMap<Integer, Lauta> paikat = new HashMap<>();
ArrayList<Lauta> M1 = new ArrayList<>();
ArrayList<Lauta> M2 = new ArrayList<>();
ArrayList<Lauta> laudat = new ArrayList<>();
int maara = Integer.parseInt(lukija.nextLine());
for (int i = 1; i <= maara; i++) {
int korkeus = lukija.nextInt();
Lauta l = new Lauta(i, korkeus);
laudat.add(l);
paikat.put(i, l);
}
Collections.sort(laudat);
int kalleinPaikka = laudat.get(0).getPaikka();
int jakojaannos1 = kalleinPaikka % 2;
for (int i = 1; i <= paikat.size(); i++) {
Lauta l = paikat.get(i);
int Jakojaannos2 = i % 2;
if (Jakojaannos2 == jakojaannos1) {
M1.add(l);
} else {
M2.add(l);
}
}
Collections.sort(M1);
Collections.sort(M2);
int Max1 = M1.get(0).getKorkeus();
int Max2 = M2.get(0).getKorkeus();
int Max22 = 0;
for (Lauta l : M2) {
if (l.getKorkeus() < Max2) {
Max22 = l.getKorkeus();
break;
}
}
int maxPalkkio = Max1 + Max2;
boolean vierekkain = false;
for (Lauta l : M1) {
int korkeus1 = l.getKorkeus();
int paikka1 = l.getPaikka();
if (korkeus1 < Max2) {
break;
}
if (paikka1 == maara) {
if (paikat.get(paikka1 - 1).getKorkeus() >= Max2) {
vierekkain = true;
break;
}
} else if (paikka1 == 1) {
if (paikat.get(paikka1 + 1).getKorkeus() >= Max2) {
vierekkain = true;
break;
}
} else if (paikat.get(paikka1 + 1).getKorkeus() >= Max2 || paikat.get(paikka1 - 1).getKorkeus() >= Max2) {
vierekkain = true;
break;
}
}
if (vierekkain) {
System.out.println(maxPalkkio + " " + 2);
for (int i = 1; i <= maara; i++) {
if (i % 2 == 1) {
System.out.print(1 + " ");
} else {
System.out.print(2 + " ");
}
}
System.out.println("");
}
Lauta max = M1.get(0);
Maalari m1 = new Maalari(1);
Maalari m2 = new Maalari(2);
Maalari m3 = new Maalari(3);
for (Lauta l : laudat) {
if (l.getPaikka() % 2 == jakojaannos1) {
l.setMaalari(m1);
m1.lisaaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
}
}
boolean maalareita3 = false;
int alaraja = 0;
int ylaraja = 0;
ArrayList<Integer> M3 = new ArrayList<>();
ArrayList<Integer> kiinnitetytPaikat = new ArrayList<>();
int paikka1 = max.getPaikka();
kiinnitetytPaikat.add(paikka1);
ArrayList<String> paras = new ArrayList<>();
paikat.values().stream().forEach((l) -> {
paras.add(l.getMaalari().getNumero());
});
while (true) {
Lauta max2lauta = m2.getLaudat().get(0);
int max2paikka = max2lauta.getPaikka();
int max2korkeus = max2lauta.getKorkeus();
paikka1 = lahinKiinnitettyEi3Valissa(max2paikka, kiinnitetytPaikat, paikat);
int paikkaero = max2paikka - paikka1;
if (Math.abs(paikkaero) != 1) {
boolean testataan = false;
if (max2paikka == 1) {
if (paikat.get(max2paikka + 1).getKorkeus() < max2korkeus) {
testataan = true;
}
} else if (max2paikka == maara) {
if (paikat.get(max2paikka - 1).getKorkeus() < max2korkeus) {
testataan = true;
}
} else if (paikat.get(max2paikka - 1).getKorkeus() < max2korkeus && paikat.get(max2paikka + 1).getKorkeus() < max2korkeus) {
testataan = true;
}
if (testataan) {
kiinnitetytPaikat.add(max2paikka);
max2lauta.setMaalari(m1);
m1.lisaaLauta(max2lauta);
m2.poistaLauta(max2lauta);
if (paikkaero < 0) {
alaraja = max2paikka;
ylaraja = paikka1;
int kolmosenPaikka = pieninValilla(alaraja, ylaraja, paikat);
Lauta la = paikat.get(kolmosenPaikka);
la.setMaalari(m3);
m3.lisaaLauta(la);
m1.poistaLauta(la);
m2.poistaLauta(la);
int jakojaannos = paikka1 % 2;
for (int i = paikka1 - 1; i > kolmosenPaikka; i--) {
Lauta l = paikat.get(i);
if (l.getPaikka() % 2 == jakojaannos) {
l.setMaalari(m1);
m1.lisaaLauta(l);
m2.poistaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
m1.poistaLauta(l);
}
}
jakojaannos = max2paikka % 2;
for (int i = kolmosenPaikka - 1; i > max2paikka; i--) {
Lauta l = paikat.get(i);
if (l.getPaikka() % 2 == jakojaannos) {
l.setMaalari(m1);
m1.lisaaLauta(l);
m2.poistaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
m1.poistaLauta(l);
}
}
for (int i = max2paikka - 1; i > 0; i--) {
Lauta l = paikat.get(i);
if (l.getPaikka() % 2 == jakojaannos) {
l.setMaalari(m1);
m1.lisaaLauta(l);
m2.poistaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
m1.poistaLauta(l);
}
}
} else {
alaraja = paikka1;
ylaraja = max2paikka;
int kolmosenPaikka = pieninValilla(alaraja, ylaraja, paikat);
Lauta la = paikat.get(kolmosenPaikka);
la.setMaalari(m3);
m3.lisaaLauta(la);
m2.poistaLauta(la);
m1.poistaLauta(la);
int jakojaannos = alaraja % 2;
for (int i = alaraja + 1; i < kolmosenPaikka; i++) {
Lauta l = paikat.get(i);
if (l.getPaikka() % 2 == jakojaannos) {
l.setMaalari(m1);
m1.lisaaLauta(l);
m2.poistaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
m1.poistaLauta(l);
}
}
jakojaannos = ylaraja % 2;
for (int i = kolmosenPaikka + 1; i < ylaraja; i++) {
Lauta l = paikat.get(i);
if (l.getPaikka() % 2 == jakojaannos) {
l.setMaalari(m1);
m1.lisaaLauta(l);
m2.poistaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
m1.poistaLauta(l);
}
}
for (int i = ylaraja + 1; i <= maara; i++) {
Lauta l = paikat.get(i);
if (l.getPaikka() % 2 == jakojaannos) {
l.setMaalari(m1);
m1.lisaaLauta(l);
m2.poistaLauta(l);
} else {
l.setMaalari(m2);
m2.lisaaLauta(l);
m1.poistaLauta(l);
}
}
}
int uusiPalkkio = m1.getPalkkio() + m2.getPalkkio() + m3.getPalkkio();
if (uusiPalkkio < maxPalkkio) {
maalareita3 = true;
maxPalkkio = uusiPalkkio;
paras.clear();
paikat.values().stream().forEach((l) -> {
paras.add(l.getMaalari().getNumero());
});
}
} else {
break;
}
} else {
break;
}
}
if (maalareita3) {
System.out.println(maxPalkkio + " " + "3");
} else {
System.out.println(maxPalkkio + " " + "2");
}
for (String a : paras) {
System.out.print(a + " ");
}
System.out.println("");
}
private static int pieninValilla(int alaraja, int ylaraja, HashMap<Integer, Lauta> paikat) {
int pienin = 1000000000;
int paikka = 0;
for (int i = alaraja; i <= ylaraja; i++) {
int korkeus = paikat.get(i).getKorkeus();
if (korkeus < pienin) {
pienin = korkeus;
paikka = i;
}
if (pienin == 1) {
break;
}
}
return paikka;
}
private static int lahinKiinnitettyEi3Valissa(int max2paikka, ArrayList<Integer> kiinnitetytPaikat, HashMap<Integer, Lauta> paikat) {
ArrayList<Integer> ehdokkaat = new ArrayList<>();
Collections.sort(kiinnitetytPaikat);
int pienilahin = 0;
int suurilahin = 0;
for (int a : kiinnitetytPaikat) {
if (a < max2paikka) {
pienilahin = a;
} else {
suurilahin = a;
break;
}
}
if (pienilahin > 0) {
ehdokkaat.add(pienilahin);
}
if (suurilahin > 0) {
ehdokkaat.add(suurilahin);
}
if (ehdokkaat.size() == 1) {
return ehdokkaat.get(0);
} else {
int paikka = pienilahin;
for (int i = pienilahin + 1; i < max2paikka; i++) {
if (paikat.get(i).getMaalari().getNumero().equals("3")) {
return suurilahin;
}
}
return pienilahin;
}
}
private static class Lauta implements Comparable<Lauta> {
private final int paikka;
private final int korkeus;
private Maalari maalari;
private Lauta(int paikka, int korkeus) {
this.paikka = paikka;
this.korkeus = korkeus;
}
private void setMaalari(Maalari m) {
this.maalari = m;
}
private Maalari getMaalari() {
return this.maalari;
}
private int getKorkeus() {
return this.korkeus;
}
private int getPaikka() {
return this.paikka;
}
@Override
public int compareTo(Lauta t) {
int ero = t.getKorkeus() - this.korkeus;
if (ero != 0) {
return t.getKorkeus() - this.korkeus;
} else {
return this.paikka - t.getPaikka();
}
}
}
private static class Maalari {
private ArrayList<Lauta> OmatLaudat;
private int palkkio;
private final int numero;
private ArrayList<Integer> paikat;
private Maalari(int numero) {
this.OmatLaudat = new ArrayList<>();
this.numero = numero;
this.paikat = new ArrayList<>();
}
private int getPalkkio() {
if (OmatLaudat == null) {
return 0;
}
Collections.sort(OmatLaudat);
this.palkkio = OmatLaudat.get(0).getKorkeus();
return this.palkkio;
}
private void lisaaLauta(Lauta l) {
this.OmatLaudat.add(l);
this.paikat.add(l.getPaikka());
}
private ArrayList<Integer> getPaikat() {
return this.paikat;
}
private ArrayList<Lauta> getLaudat() {
Collections.sort(OmatLaudat);
return this.OmatLaudat;
}
private String getNumero() {
return Integer.toString(this.numero);
}
private void poistaLauta(Lauta la) {
OmatLaudat.remove(la);
}
}
}
Test details
Test 1
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 10 22 54 3 91 69 90 40 29 83 71 |
| correct output |
|---|
| 174 3 2 1 2 1 2 1 2 1 2 1 |
| user output |
|---|
| 174 2 2 1 2 1 2 1 2 1 2 1 |
Test 2
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 10 49 3 96 38 90 18 92 74 83 1 |
| correct output |
|---|
| 170 3 1 2 1 2 1 2 1 2 1 2 |
| user output |
|---|
| 170 2 1 2 1 2 1 2 1 2 1 2 170 2 1 2 1 2 1 2 1 2 1 2 |
Test 3
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 10 46 3 41 30 16 17 12 93 80 81 |
| correct output |
|---|
| 173 3 2 1 2 1 2 1 2 1 2 1 |
| user output |
|---|
| 173 2 1 2 1 2 1 2 1 2 1 2 173 2 2 1 2 1 2 1 2 1 2 1 |
Test 4
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 10 46 8 95 85 82 73 82 92 53 90 |
| correct output |
|---|
| 187 3 1 2 1 2 1 2 1 2 1 2 |
| user output |
|---|
| 187 2 1 2 1 2 1 2 1 2 1 2 |
Test 5
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 10 41 18 61 59 40 96 5 2 74 38 |
| correct output |
|---|
| 159 3 2 1 2 1 2 1 2 3 1 2 |
| user output |
|---|
| 159 3 2 1 2 1 2 1 2 3 1 2 |
Test 6
Group: 1
Verdict: ACCEPTED
| input |
|---|
| 10 1 1 1 1 1 1 1 1 1 1 |
| correct output |
|---|
| 2 3 2 1 2 1 2 1 2 1 2 1 |
| user output |
|---|
| 2 2 1 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1 2 1 2 1 2 |
Test 7
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 100 1 39 94 5 24 84 84 10 78 61 38... |
| correct output |
|---|
| 193 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| 193 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 8
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 100 31 73 18 88 49 28 66 5 32 48 9... |
| correct output |
|---|
| 199 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| 199 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 9
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 100 45 56 36 60 31 10 23 79 29 17 ... |
| correct output |
|---|
| 198 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| 198 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 10
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 100 1 77 70 62 21 68 40 54 90 62 1... |
| correct output |
|---|
| 194 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| 194 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
Test 11
Group: 2
Verdict: WRONG ANSWER
| input |
|---|
| 100 4 47 41 81 56 64 12 10 20 100 ... |
| correct output |
|---|
| 189 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| 196 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 12
Group: 2
Verdict: ACCEPTED
| input |
|---|
| 10 1 1 1 1 1 1 1 1 1 1 |
| correct output |
|---|
| 2 3 2 1 2 1 2 1 2 1 2 1 |
| user output |
|---|
| 2 2 1 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1 2 1 2 1 2 |
Test 13
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100 256160448 813097800 167146270 ... |
| correct output |
|---|
| 1929869257 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| -2070967995 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 14
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 100 520002672 3542567 24668528 959... |
| correct output |
|---|
| 1946957555 3 1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| 1946957555 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 15
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 100 483158423 780224665 844754665 ... |
| correct output |
|---|
| 1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| 1959373560 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
Test 16
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100 969647264 128558017 889036329 ... |
| correct output |
|---|
| 1997942264 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| -1796290309 3 1 2 1 2 1 2 1 2 1 2 1 3 1 2 1 ... |
Test 17
Group: 3
Verdict: WRONG ANSWER
| input |
|---|
| 100 745018527 400495893 635468795 ... |
| correct output |
|---|
| 1961391143 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| -1509310957 3 1 2 1 2 1 2 1 2 1 3 2 1 2 1 2 ... |
Test 18
Group: 3
Verdict: ACCEPTED
| input |
|---|
| 10 1 1 1 1 1 1 1 1 1 1 |
| correct output |
|---|
| 2 3 2 1 2 1 2 1 2 1 2 1 |
| user output |
|---|
| 2 2 1 2 1 2 1 2 1 2 1 2 2 2 1 2 1 2 1 2 1 2 1 2 |
Test 19
Group: 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 197349274 775463806 263930657 ... |
| correct output |
|---|
| 1999942635 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| (empty) |
Test 20
Group: 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 102296405 34648120 320393597 9... |
| correct output |
|---|
| 1999930943 3 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ... |
| user output |
|---|
| (empty) |
Test 21
Group: 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 781254921 418252056 502363453 ... |
| correct output |
|---|
| 1999987794 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| (empty) |
Test 22
Group: 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 849784881 230439009 455097426 ... |
| correct output |
|---|
| 1999979439 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| (empty) |
Test 23
Group: 4
Verdict: TIME LIMIT EXCEEDED
| input |
|---|
| 100000 851456132 13422224 537539701 4... |
| correct output |
|---|
| 1999948226 3 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |
| user output |
|---|
| (empty) |
Test 24
Group: 4
Verdict: ACCEPTED
| input |
|---|
| 100000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ... |
| correct output |
|---|
| 2 3 3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ... |
| user output |
|---|
| 2 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ... |