import java.io.*;
import java.util.*;
public class lego {
static class InputReader {
public BufferedReader reader;
public StringTokenizer tokenizer;
public InputReader(InputStream stream) {
reader = new BufferedReader(new InputStreamReader(stream), 32768);
tokenizer = null;
}
public String next() {
while (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public int nextInt() {
return Integer.parseInt(next());
}
}
static class Cell {
public int x, y;
public Cell() {}
public Cell(int x_, int y_) {
x = x_;
y = y_;
}
static long hash_combine(long h_first, long h_second) {
return h_first ^ (h_second + (long)0x9e3779b9 + (h_first << 6) + (h_second >> 2));
}
static long hash_int(long x) {
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = ((x >> 16) ^ x) * 0x45d9f3b;
x = (x >> 16) ^ x;
return x;
}
@Override
public int hashCode() {
long h_first = hash_int(x & 0xFFFFFFFFL);
long h_second = hash_int(y & 0xFFFFFFFFL);
return (int)hash_combine(h_first, h_second);
}
@Override
public boolean equals(Object obj) {
if (getClass() != obj.getClass()) return false;
Cell c = (Cell)obj;
return x == c.x && y == c.y;
}
}
static class LegoSolver {
int N, V;
Cell[] cells, empty_cells;
Map<Cell, Integer> cell_indices, empty_cell_indices;
boolean[] removed;
SortedSet<Integer> removable;
boolean[] is_removable;
List<Integer>[] G4;
int[][] G8;
void construct_graphs(boolean only_solvability) {
int[] dx = {-1, -1, -1, 0, 1, 1, 1, 0};
int[] dy = { 1, 0, -1, -1, -1, 0, 1, 1};
if (!init_solvability_done) {
for (int i = 0; i < N; i++) for (int j = 0; j < 8; j++) {
Cell p = new Cell(cells[i].x + dx[j], cells[i].y + dy[j]);
Integer it = cell_indices.get(p);
int cell_id = (it == null) ? -1 : it;
if (cell_id == -1) {
Integer jt = empty_cell_indices.get(p);
if (jt == null) {
empty_cell_indices.put(p, V-N);
cell_id = V;
empty_cells[V-N] = p;
G4[V] = new ArrayList<Integer>(4);
for(int k = 0; k < 8; k++) G8[V][k] = V;
V++;
}
else cell_id = N + jt;
G8[cell_id][4^j] = i;
if (j % 2 != 0) G4[cell_id].add(i);
}
G8[i][j] = cell_id;
if (j % 2 != 0) G4[i].add(cell_id);
}
}
if (!init_done && !only_solvability) {
for (int i = 0; i < V-N; i++) for (int j = 0; j < 8; j++) {
if (G8[N+i][j] != N+i) continue;
Cell p = new Cell(empty_cells[i].x + dx[j], empty_cells[i].y + dy[j]);
Integer it = empty_cell_indices.get(p);
if (it == null) continue;
int cell_id = N + it;
G8[N+i][j] = cell_id;
if (j % 2 != 0) G4[N+i].add(cell_id);
}
}
}
void construct_graphs() { construct_graphs(false); }
int outer_component;
List<Integer>[] components4, components8;
int[] comp4, comp8;
int[] deg4, deg8; // degree = number of full neighbouring cells
void find_components(boolean only_solvability) {
Queue<Integer> q = new LinkedList<Integer>();
if (!init_solvability_done) {
components4 = new ArrayList[V];
components8 = new ArrayList[V];
comp4 = new int[V];
comp8 = new int[V];
deg4 = new int[V];
deg8 = new int[V];
for (int i = 0; i < V; i++) {
comp4[i] = comp8[i] = -1;
deg4[i] = deg8[i] = 0;
}
for (int i = 0; i < V; i++) if (comp8[i] == -1 && !is_empty(i)) {
comp8[i] = i;
components8[i] = new ArrayList<Integer>(1);
components8[i].add(i);
q.add(i);
while (!q.isEmpty()) {
int u = q.remove();
for (int v : G8[u]) if (comp8[v] == -1 && !is_empty(v)) {
comp8[v] = i;
components8[i].add(v);
q.add(v);
}
}
}
}
if (!init_done && !only_solvability) {
for (int i = 0; i < V; i++) if (comp4[i] == -1 && is_empty(i)) {
comp4[i] = i;
components4[i] = new ArrayList<Integer>(1);
components4[i].add(i);
q.add(i);
while (!q.isEmpty()) {
int u = q.remove();
for (int v : G4[u]) if (comp4[v] == -1 && is_empty(v)) {
comp4[v] = i;
components4[i].add(v);
q.add(v);
}
}
}
for (int i = 0; i < V; i++) {
for (int v : G4[i]) if (!is_empty(v)) deg4[i]++;
for (int v : G8[i]) if (!is_empty(v)) deg8[i]++;
}
}
}
void find_components() { find_components(false); }
void add_edge(int v1, int v2) {
int c1 = comp4[v1], c2 = comp4[v2];
if (c1 == c2) return;
if (components4[c1].size() < components4[c2].size()) {int tmp = c1; c1 = c2; c2 = tmp;}
for (int v : components4[c2]) {
comp4[v] = c1;
components4[c1].add(v);
}
if (c2 == outer_component) outer_component = c1;
for (int v : components4[c2])
for (int f : G8[v]) if (!is_empty(f)) update(f);
}
static byte[] seen;
void update(int v) {
boolean reachable = false, articulation = false;
for (int adj : G4[v]) if (is_empty(adj))
if (comp4[adj] == outer_component) reachable = true;
if (deg8[v] <= 1) {
if (reachable) {
if (!is_removable[v]) {
removable.add(v);
is_removable[v] = true;
}
}
else if (is_removable[v]) {
removable.remove(v);
is_removable[v] = false;
}
return;
}
for (int j = 0; j < 8; j++) if (is_empty(G8[v][j])) {
if (is_empty(G8[v][(j+1)%8])) continue; // 1 cell per region
if (j % 2 == 0 && !is_empty(G8[v][(j+7)%8])) continue; // ignore corner gaps
int c = comp4[G8[v][j]];
if (seen[c] >= 1) {
articulation = true;
break;
}
seen[c]++;
}
for (int j = 0; j < 8; j++) if (is_empty(G8[v][j]))
seen[comp4[G8[v][j]]] = 0;
if (reachable && !articulation) {
if (!is_removable[v]) {
removable.add(v);
is_removable[v] = true;
}
}
else if (is_removable[v]) {
removable.remove(v);
is_removable[v] = false;
}
}
boolean is_empty(int cell) {
return (cell >= N || removed[cell]);
}
boolean init_done, init_solvability_done;
void init_solvability() {
if (init_solvability_done) return;
construct_graphs(true);
removed = new boolean[V];
seen = new byte[V];
for (int i = 0; i < V; i++) {
seen[i] = 0;
removed[i] = false;
}
find_components(true);
init_solvability_done = true;
}
void init() {
if (init_done) return;
construct_graphs();
if (!init_solvability_done) {
removed = new boolean[V];
for (int i = 0; i < V; i++) removed[i] = false;
}
find_components();
int min_coord = cells[0].x;
for (int i = N; i < V; i++) if (min_coord >= empty_cells[i-N].x) {
min_coord = empty_cells[i-N].x;
outer_component = comp4[i];
}
is_removable = new boolean[N];
removable = new TreeSet<Integer>();
for (int i = 0; i < N; i++) {
is_removable[i] = false;
update(i);
}
init_done = init_solvability_done = true;
}
public LegoSolver(List<Cell> cells_) {
N = cells_.size();
cells = new Cell[N];
empty_cells = new Cell[8*N];
cell_indices = new HashMap<Cell, Integer>(N);
empty_cell_indices = new HashMap<Cell, Integer>(8*N);
for (int i = 0; i < N; i++) {
cells[i] = cells_.get(i);
cell_indices.put(cells[i], i);
}
G4 = new ArrayList[9*N];
G8 = new int[9*N][8];
V = N;
for (int i = 0; i < N; i++) {
G4[i] = new ArrayList<Integer>(4);
}
init_done = init_solvability_done = false;
}
public boolean solvable() {
init_solvability();
return (components8[comp8[0]].size() == N);
}
public int remove() {
init();
if (removable.isEmpty()) return -1;
int rm_id = removable.last();
removable.remove(rm_id);
removed[rm_id] = true;
components4[rm_id] = new ArrayList<Integer>(1);
components4[rm_id].add(rm_id);
comp4[rm_id] = rm_id;
for (int f : G4[rm_id]) if (!is_empty(f)) update(f);
for (int v : G4[rm_id]) {
if (is_empty(v)) add_edge(rm_id, v);
else deg4[v]--;
}
for (int v : G8[rm_id]) {
deg8[v]--;
if (!is_empty(v)) update(v);
}
return rm_id;
}
}
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
InputReader in = new InputReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
int N = in.nextInt();
int t = in.nextInt();
List<Cell> cells = new ArrayList<Cell>(N);
for (int i = 0; i < N; i++) {
Cell c = new Cell();
c.x = in.nextInt();
c.y = in.nextInt();
cells.add(c);
}
LegoSolver solver = new LegoSolver(cells);
if (!solver.solvable()) {
out.println("NO");
out.close();
return;
}
out.println("YES");
int[] build = new int[N];
for (int i = 0; i < N; i++) {
int removed_cell_id = solver.remove();
build[i] = removed_cell_id+1;
}
for (int i = 0; i < N; i++) out.println(build[N-1-i]);
out.close();
}
}
Compilation message
skyscrapers.java:4: error: class lego is public, should be declared in a file named lego.java
public class lego {
^
Note: skyscrapers.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
