— Dark mode

Datatähti 2017 alku

Maalarit

  • Start: 2016-10-03 00:00:00
  • End: 2016-10-17 00:00:00
CSES - Datatähti 2017 alku - Results
Submission details
Task:Maalarit
Sender:kh
Submission time:2016-10-13 17:00:06 +0300
Language:Java
Status:READY
Result:37
Feedback
groupverdictscore
#1ACCEPTED12
#2ACCEPTED25
#30
#40
Test results
testverdicttimegroup
#1ACCEPTED0.23 s1details
#2ACCEPTED0.12 s1details
#3ACCEPTED0.15 s1details
#4ACCEPTED0.24 s1details
#5ACCEPTED0.23 s1details
#6ACCEPTED0.14 s1details
#7ACCEPTED0.28 s2details
#8ACCEPTED0.28 s2details
#9ACCEPTED0.27 s2details
#10ACCEPTED0.17 s2details
#11ACCEPTED0.29 s2details
#12ACCEPTED0.14 s2details
#13ACCEPTED0.26 s3details
#14ACCEPTED0.26 s3details
#15ACCEPTED0.28 s3details
#16ACCEPTED0.28 s3details
#170.29 s3details
#18ACCEPTED0.14 s3details
#19--4details
#20--4details
#21--4details
#22--4details
#23--4details
#24ACCEPTED0.93 s4details

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 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("");
        } else {
            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> kiinnitetytPaikat = new ArrayList<>();
            int paikka1;
            kiinnitetytPaikat.add(laudat.get(0).getPaikka());
            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);
                                }

                            }

                        }
                        long uusiPalkkio = (long) m1.getPalkkio() + m2.getPalkkio() + m3.getPalkkio();
                        if (uusiPalkkio < maxPalkkio) {
                            maalareita3 = true;
                            maxPalkkio = (int) 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");
            }
            paras.stream().forEach((a) -> {
                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 {
            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 Maalari(int numero) {
            this.OmatLaudat = new ArrayList<>();
            this.numero = numero;
        }

        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) {
            if (!this.OmatLaudat.contains(l)) {
                this.OmatLaudat.add(l);
            }
        }

        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
view save

correct output
174 3
2 1 2 1 2 1 2 1 2 1 
view save

user output
174 2
2 1 2 1 2 1 2 1 2 1 
view save

Test 2

Group: 1

Verdict: ACCEPTED

input
10
49 3 96 38 90 18 92 74 83 1
view save

correct output
170 3
1 2 1 2 1 2 1 2 1 2 
view save

user output
170 2
1 2 1 2 1 2 1 2 1 2 
view save

Test 3

Group: 1

Verdict: ACCEPTED

input
10
46 3 41 30 16 17 12 93 80 81
view save

correct output
173 3
2 1 2 1 2 1 2 1 2 1 
view save

user output
173 2
1 2 1 2 1 2 1 2 1 2 
view save

Test 4

Group: 1

Verdict: ACCEPTED

input
10
46 8 95 85 82 73 82 92 53 90
view save

correct output
187 3
1 2 1 2 1 2 1 2 1 2 
view save

user output
187 2
1 2 1 2 1 2 1 2 1 2 
view save

Test 5

Group: 1

Verdict: ACCEPTED

input
10
41 18 61 59 40 96 5 2 74 38
view save

correct output
159 3
2 1 2 1 2 1 2 3 1 2 
view save

user output
159 3
2 1 2 1 2 1 2 3 1 2 
view save

Test 6

Group: 1

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1
view save

correct output
2 3
2 1 2 1 2 1 2 1 2 1 
view save

user output
2 2
1 2 1 2 1 2 1 2 1 2 
view save

Test 7

Group: 2

Verdict: ACCEPTED

input
100
1 39 94 5 24 84 84 10 78 61 38...
view save

correct output
193 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
193 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

Test 8

Group: 2

Verdict: ACCEPTED

input
100
31 73 18 88 49 28 66 5 32 48 9...
view save

correct output
199 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
199 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

Test 9

Group: 2

Verdict: ACCEPTED

input
100
45 56 36 60 31 10 23 79 29 17 ...
view save

correct output
198 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
198 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

Test 10

Group: 2

Verdict: ACCEPTED

input
100
1 77 70 62 21 68 40 54 90 62 1...
view save

correct output
194 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
194 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

Test 11

Group: 2

Verdict: ACCEPTED

input
100
4 47 41 81 56 64 12 10 20 100 ...
view save

correct output
189 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
189 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

Test 12

Group: 2

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1
view save

correct output
2 3
2 1 2 1 2 1 2 1 2 1 
view save

user output
2 2
1 2 1 2 1 2 1 2 1 2 
view save

Test 13

Group: 3

Verdict: ACCEPTED

input
100
256160448 813097800 167146270 ...
view save

correct output
1929869257 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
1929869257 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

Test 14

Group: 3

Verdict: ACCEPTED

input
100
520002672 3542567 24668528 959...
view save

correct output
1946957555 3
1 2 3 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
1946957555 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

Test 15

Group: 3

Verdict: ACCEPTED

input
100
483158423 780224665 844754665 ...
view save

correct output
1959373560 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
1959373560 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

Test 16

Group: 3

Verdict: ACCEPTED

input
100
969647264 128558017 889036329 ...
view save

correct output
1997942264 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
1997942264 2
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

Test 17

Group: 3

Verdict:

input
100
745018527 400495893 635468795 ...
view save

correct output
1961391143 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
1983812469 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

Test 18

Group: 3

Verdict: ACCEPTED

input
10
1 1 1 1 1 1 1 1 1 1
view save

correct output
2 3
2 1 2 1 2 1 2 1 2 1 
view save

user output
2 2
1 2 1 2 1 2 1 2 1 2 
view save

Test 19

Group: 4

Verdict:

input
100000
197349274 775463806 263930657 ...
view save

correct output
1999942635 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
(empty)

Test 20

Group: 4

Verdict:

input
100000
102296405 34648120 320393597 9...
view save

correct output
1999930943 3
2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 ...
view save

user output
(empty)

Test 21

Group: 4

Verdict:

input
100000
781254921 418252056 502363453 ...
view save

correct output
1999987794 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
(empty)

Test 22

Group: 4

Verdict:

input
100000
849784881 230439009 455097426 ...
view save

correct output
1999979439 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

user output
(empty)

Test 23

Group: 4

Verdict:

input
100000
851456132 13422224 537539701 4...
view save

correct output
1999948226 3
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

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 ...
view save

correct output
2 3
3 1 3 1 3 1 3 1 3 1 3 1 3 1 3 ...
view save

user output
2 2
1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 ...
view save

Tasks

A Pakkaus-B Bittijono-C Kolikot-D Järjestys-E Maalarit-

Submissions (kh)

2016-10-16 21:29:22 682016-10-16 21:02:14 682016-10-16 14:19:47 682016-10-16 14:09:25 682016-10-15 15:25:58 122016-10-15 15:21:00 372016-10-15 15:19:57 122016-10-15 15:08:24 372016-10-15 14:52:41 372016-10-15 14:23:10 122016-10-14 18:27:48 122016-10-13 17:55:58 122016-10-13 17:51:18 122016-10-13 17:39:33 122016-10-13 17:00:06 372016-10-11 21:27:57 372016-10-11 20:47:58 122016-10-11 20:46:45 122016-10-11 20:45:37 122016-10-11 20:31:16 122016-10-11 20:26:33 122016-10-11 19:44:34 122016-10-06 16:40:31 0