CSES - Datatähti Open 2017 - Results
Submission details
Task:Mex value
Sender:ruhanhabib39
Submission time:2017-01-20 17:41:58 +0200
Language:Java
Status:READY
Result:100
Feedback
groupverdictscore
#1ACCEPTED28
#2ACCEPTED72
Test results
testverdicttimegroup
#1ACCEPTED0.14 s1details
#2ACCEPTED0.14 s1details
#3ACCEPTED0.13 s1details
#4ACCEPTED0.15 s1details
#5ACCEPTED0.12 s1details
#6ACCEPTED0.13 s1details
#7ACCEPTED0.12 s1details
#8ACCEPTED0.13 s1details
#9ACCEPTED0.15 s1details
#10ACCEPTED0.12 s1details
#11ACCEPTED0.55 s2details
#12ACCEPTED0.56 s2details
#13ACCEPTED0.60 s2details
#14ACCEPTED0.56 s2details
#15ACCEPTED0.54 s2details
#16ACCEPTED0.57 s2details
#17ACCEPTED0.57 s2details
#18ACCEPTED0.66 s2details
#19ACCEPTED0.61 s2details
#20ACCEPTED0.54 s2details

Code

import java.io.*;
import java.util.*;

public class B {
   public static void main(String[] args) throws IOException {
      BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
      (new B()).solve(in, out);
      out.close();
   }

   private int n, k;
   private int[] x;
   private TreeSet<Integer> mex;
   private Map<Integer,Integer> mp;
   private int res = 0;

   private void add(int num) {
      // System.err.println("add\nnum = " + num);
      // System.err.println("res = " + res);
      Integer cc = mp.get(num);
      if(cc == null) {
         mex.remove(num);
         mp.put(num, 1);
      } else {
         mp.put(num, cc + 1);
      }
      res = mex.first();
   }

   private void rem(int num) {
      // System.err.println("rem\nnum = " + num);
      // System.err.println("res = " + res);
      int cc = mp.get(num); cc--;
      mp.put(num, cc);
      if(cc == 0) {
         mex.add(num); mp.remove(num);
      }
      res = mex.first();
   }

   public void solve(BufferedReader in, PrintWriter out) throws IOException {
      String[] tok = in.readLine().split(" ");
      n = Integer.parseInt(tok[0]);
      k = Integer.parseInt(tok[1]);
      tok = in.readLine().split(" ");
      x = new int[tok.length];

      for(int i = 0; i < x.length; i++) {
         x[i] = Integer.parseInt(tok[i]);
      }

      mex = new TreeSet<Integer>();
      mex.add(0);

      for(int num : x) {
         mex.add(num+1); mex.add(num);
      }

      mp = new HashMap<Integer,Integer>();

      for(int i = 0; i < k; i++) {
         add(x[i]);
      }

      out.print(res);

      for(int l = 1; l+k-1 < x.length; l++) {
         // System.err.println("[ " + l + ", " + (l+k-1) + "]");
         rem(x[l-1]); add(x[l+k-1]);
         out.print(" " + res);
      }

      out.println();
   }
}

Test details

Test 1

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 9 1 0 5 7 2 8 6 3 4...

correct output
4 10 9 1 1 1 1 1 1 1 1 4 10 3 ...

user output
4 10 9 1 1 1 1 1 1 1 1 4 10 3 ...

Test 2

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 4 3 8 1 0 9 5 7 2 6...

correct output
6 10 4 3 3 1 1 1 1 1 3 3 10 6 ...

user output
6 10 4 3 3 1 1 1 1 1 3 3 10 6 ...

Test 3

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 9 2 3 1 0 8 5 6 4 7...

correct output
7 10 9 2 2 1 0 1 1 1 2 9 10 4 ...

user output
7 10 9 2 2 1 0 1 1 1 2 9 10 4 ...

Test 4

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 3 0 4 6 5 7 1 2 8 9...

correct output
9 10 3 0 0 0 0 0 4 2 2 2 10 6 ...

user output
9 10 3 0 0 0 0 0 4 2 2 2 10 6 ...

Test 5

Group: 1

Verdict: ACCEPTED

input
100 10
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 ...

correct output
10 10 10 10 10 10 10 10 10 10 ...

user output
10 10 10 10 10 10 10 10 10 10 ...

Test 6

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 0 5 1 9 3 4 6 7 2 8...

correct output
8 10 0 5 1 1 1 1 1 5 2 5 10 0 ...

user output
8 10 0 5 1 1 1 1 1 5 2 5 10 0 ...

Test 7

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 1 2 9 3 8 0 4 7 5 6...

correct output
6 10 1 1 1 1 2 0 0 2 3 9 10 6 ...

user output
6 10 1 1 1 1 2 0 0 2 3 9 10 6 ...

Test 8

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 5 0 6 7 1 4 8 3 9 2...

correct output
2 10 5 0 0 0 0 0 0 0 0 1 10 9 ...

user output
2 10 5 0 0 0 0 0 0 0 0 1 10 9 ...

Test 9

Group: 1

Verdict: ACCEPTED

input
100 10
1000000000 7 3 0 1 4 9 2 5 6 8...

correct output
8 10 7 3 0 0 0 0 7 5 5 5 10 8 ...

user output
8 10 7 3 0 0 0 0 7 5 5 5 10 8 ...

Test 10

Group: 1

Verdict: ACCEPTED

input
100 10
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 ...

correct output
10 10 10 10 10 10 10 10 10 10 ...

user output
10 10 10 10 10 10 10 10 10 10 ...

Test 11

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 4786 3512 3285 1919...

correct output
9547 10000 4786 3512 3285 1919...

user output
9547 10000 4786 3512 3285 1919...

Test 12

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 7981 3955 790 45 34...

correct output
7657 10000 7981 3955 790 45 45...

user output
7657 10000 7981 3955 790 45 45...

Test 13

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2329 1825 9435 3800...

correct output
5701 10000 2329 1825 1825 1825...

user output
5701 10000 2329 1825 1825 1825...

Test 14

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2754 6029 8007 6286...

correct output
1423 10000 2754 2754 2754 2754...

user output
1423 10000 2754 2754 2754 2754...

Test 15

Group: 2

Verdict: ACCEPTED

input
100000 10000
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
10000 10000 10000 10000 10000 ...

user output
10000 10000 10000 10000 10000 ...

Test 16

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 7560 4634 7044 3853...

correct output
9855 10000 7560 4634 4634 3853...

user output
9855 10000 7560 4634 4634 3853...

Test 17

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 7945 6674 3975 3002...

correct output
6373 10000 7945 6674 3975 3002...

user output
6373 10000 7945 6674 3975 3002...

Test 18

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2506 6827 6871 8593...

correct output
2978 10000 2506 2506 2506 2506...

user output
2978 10000 2506 2506 2506 2506...

Test 19

Group: 2

Verdict: ACCEPTED

input
100000 10000
1000000000 2769 5036 539 4409 ...

correct output
2249 10000 2769 2769 539 539 5...

user output
2249 10000 2769 2769 539 539 5...

Test 20

Group: 2

Verdict: ACCEPTED

input
100000 10000
0 1 2 3 4 5 6 7 8 9 10 11 12 1...

correct output
10000 10000 10000 10000 10000 ...

user output
10000 10000 10000 10000 10000 ...