fork download
copy 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.ArrayList;
  6. import java.util.Arrays;
  7. import java.util.Collections;
  8. import java.util.List;
  9. import java.util.StringTokenizer;
  10.  
  11. public class Main {
  12.     private BufferedReader in;
  13.     private StringTokenizer tok;
  14.     private PrintWriter out;
  15.  
  16.     //------------------------------------------------------------------------------
  17.     public static void main(String[] args) {
  18.         new Main().run();
  19.     }
  20.  
  21.     final static int INF = (int) 1e9;
  22.  
  23.     private void solve() throws IOException {
  24.         int n = readInt();
  25.         int k = readInt();
  26.         int[] a = new int[n];
  27.         for (int i = 0; i < n; i++) {
  28.             a[i] = readInt() - 1;
  29.         }
  30.  
  31.         //noinspection unchecked
  32.         List<Integer>[] positions = new List[k];
  33.         for (int i = 0; i < k; i++) {
  34.             positions[i] = new ArrayList<>();
  35.         }
  36.         for (int i = 0; i < n; i++) {
  37.             positions[a[i]].add(i);
  38.         }
  39.  
  40.         if (positions[0].isEmpty()) {
  41.             out.println(0);
  42.             return;
  43.         }
  44.  
  45.         int[] dp = new int[n + 1];
  46.         boolean[] parentIsRemoved = new boolean[n + 1];
  47.         int[] parentPrevIndex = new int[n + 1];
  48.         Arrays.fill(dp, INF);
  49.         Arrays.fill(parentPrevIndex, -1);
  50.         dp[positions[0].get(0)] = 0;
  51.         for (int value = 0; value < k; value++) {
  52.             for (int i = 0; i < positions[value].size(); i++) {
  53.                 int index = positions[value].get(i);
  54.  
  55.                 {
  56.                     int nextSameIndex;
  57.                     if (i == positions[value].size() - 1) {
  58.                         nextSameIndex = n;
  59.                     } else {
  60.                         nextSameIndex = positions[value].get(i + 1);
  61.                     }
  62.                     if (dp[nextSameIndex] > dp[index] + 1) {
  63.                         dp[nextSameIndex] = dp[index] + 1;
  64.                         parentIsRemoved[nextSameIndex] = true;
  65.                         parentPrevIndex[nextSameIndex] = index;
  66.                     }
  67.                 }
  68.  
  69.                 if (value < k - 1) {
  70.                     int bsPos = ~Collections.binarySearch(positions[value + 1], index);
  71.                     int nextIncIndex;
  72.                     if (bsPos == positions[value + 1].size()) {
  73.                         nextIncIndex = n;
  74.                     } else {
  75.                         nextIncIndex = positions[value + 1].get(bsPos);
  76.                     }
  77.                     if (dp[nextIncIndex] > dp[index]) {
  78.                         dp[nextIncIndex] = dp[index];
  79.                         parentIsRemoved[nextIncIndex] = false;
  80.                         parentPrevIndex[nextIncIndex] = index;
  81.                     }
  82.                 }
  83.             }
  84.         }
  85.  
  86.         List<Integer> ans = new ArrayList<>();
  87.         int now = n;
  88.         //noinspection ConditionalBreakInInfiniteLoop
  89.         while (true) {
  90.             if (now == -1) {
  91.                 break;
  92.             }
  93.             if (parentIsRemoved[now]) {
  94.                 ans.add(parentPrevIndex[now]);
  95.             }
  96.             now = parentPrevIndex[now];
  97.         }
  98.         if (ans.size() != dp[n]) {
  99.             throw new AssertionError();
  100.         }
  101.  
  102.         Collections.sort(ans);
  103.         out.println(ans.size());
  104.         for (int index : ans) {
  105.             out.print((index + 1) + " ");
  106.         }
  107.         out.println();
  108.     }
  109.  
  110.     private void run() {
  111.         try {
  112.             initIO();
  113.             solve();
  114.             in.close();
  115.             out.close();
  116.         } catch (Throwable e) {
  117.             throw new RuntimeException(e);
  118.         }
  119.     }
  120.  
  121.     @SuppressWarnings("RedundantThrows")
  122.     private void initIO() throws IOException {
  123.         in = new BufferedReader(new InputStreamReader(System.in));
  124.         out = new PrintWriter(System.out);
  125. //        in = new BufferedReader(new FileReader(new File("input.txt")));
  126. //        out = new PrintWriter(new File("output.txt"));
  127.     }
  128.  
  129.     private String readString() throws IOException {
  130.         while (tok == null || !tok.hasMoreTokens()) {
  131.             tok = new StringTokenizer(in.readLine());
  132.         }
  133.         return tok.nextToken();
  134.     }
  135.  
  136.     @SuppressWarnings("unused")
  137.     private int readInt() throws IOException {
  138.         return Integer.parseInt(readString());
  139.     }
  140.  
  141.     @SuppressWarnings("unused")
  142.     private long readLong() throws IOException {
  143.         return Long.parseLong(readString());
  144.     }
  145.  
  146.     @SuppressWarnings("unused")
  147.     private double readDouble() throws IOException {
  148.         return Double.parseDouble(readString());
  149.     }
  150. }
  151.  
Success #stdin #stdout 0.14s 34156KB
comments (?)
stdin
copy 
3 2
1 2 2
stdout
copy 
1
1
https://ideone.com/JzapyX
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!