Submission #306178

#	Time	Username	Problem	Language	Result	Execution time	Memory
306178		model_code	Painting Squares (IOI20_squares)	Java	75 / 100	1053 ms	28148 KiB

squares

import java.util.ArrayList;

public class squares {
  
  private int[] visited = null, reverse_map = null;
  private ArrayList<Integer> euler_path = null, labels = null;

  void dfs(int x) {
    while (visited[x] < 2) {
      dfs((x >> 1) | (visited[x]++ << 8));
    }
    euler_path.add(x);
  }
  
  void generate_map() {
    visited = new int[512];
    euler_path = new ArrayList<>();
    dfs(0);
    labels = new ArrayList<>();
    for (int i = 0; i < 8; i++) {
      labels.add(0);
    }
    reverse_map = new int[1024];
    for (int i = 0; i < euler_path.size() - 1; i++) {
      labels.add(euler_path.get(i) & 1);
      reverse_map[(euler_path.get(i) << 1) | (euler_path.get(i + 1) & 1)] = i;
    }
  }
  
  int[] paint(int n) {
    if (euler_path == null) {
      generate_map();
    }
    int[] painting = new int[n + 1];
    for (int i = 0; i < n; i++) {
      painting[i] = labels.get(i);
    }
    painting[n] = 10;
  	return painting;
  }

  int find_location(int n, int[] c) {
    if (euler_path == null) {
      generate_map();
    }
    int val = 0;
    for (int i = 0; i < c.length; i++) {
      if (c[i] == -1) return n - i;
      val = (val << 1) | c[i];
    }
    return reverse_map[val];
  }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 20 / 20
• Subtask 4: 55 / 55