| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 697632 | vjudge1 | Evacuation plan (IZhO18_plan) | Java | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
public class tank {
static int mod = 998244353;
static int mod2 = (int) 1e9 + 7;
static long[][] st;
static long[][] stt;
static long[] tit;
static int[] tout;
static int s[];
static int N = (int) 2e5 + 500;
static int a[] = new int[N];
static int t[] ;
static int ans[];
static long arr[];
static long as[];
static FastReader sc = new FastReader(System.in);
static PrintWriter out = new PrintWriter(System.out);
static int [][]check;
static int timer=2;
static int anss=0;
static long mosdo=1073741824;
public static void main(String[] args) throws IOException {
//int tt = sc.nextInt();
int tt = 1;
Gr1zler:
for (int WTF = 0; WTF < tt; WTF++) {
int m=sc.nextInt();
int n=sc.nextInt();
int as[]=new int[m];
int s1[]=new int[n+1];
Arrays.fill(s1,-1);
for(int i=0;i<m;i++){
as[i]=sc.nextInt();
s1[as[i]]=i;
}
boolean check[]=new boolean[n+1];
int ass[][]=new int[2][m];
StringBuilder scc=new StringBuilder();
int count=0;
for(int i=0;i<m;i++){
if(!check[as[i]]){
ass[0][i]++;
ass[1][s1[as[i]]]++;
check[as[i]]=true;
count++;
scc.append(as[i]+" "+(i+1)+" "+(s1[as[i]]+1)+"\n");
}
}
Stack<Integer>ds=new Stack<>();
boolean checker=true;
for(int i=0;i<m;i++){
if(ass[0][i]==1){
ds.add(as[i]);
}
if(as[i]!=ds.peek()){
checker=false;
}
if(ass[1][i]==1){
ds.pop();
}
}
// System.out.println(Arrays.toString(ass[0]));
// System.out.println(Arrays.toString(ass[1]));
if(checker){
out.println(count);
out.println(scc.toString());
}else{
out.println(-1);
}
}
out.close();
}
static int checkker(int u,int ul,int ur,int l){
//System.out.println(ul+" "+ur+" "+t[u]);
if(ur<l){
return 0;
}
if(ul>=l){
return t[u];
}
int mid=(ul+ur)/2;
return Math.max(checkker(u*2,ul,mid,l),checkker(u*2+1,mid+1,ur,l));
}
static void built(int u,int l,int r,int i,int a){
if(i>r||i<l){
return;
}
if(l==r){
t[u]=a;
return ;
}
int m=(l+r)/2;
built(u*2,l,m,i,a);
built(u*2+1,m+1,r,i,a);
t[u]=Math.max(t[u*2],t[u*2+1]);
}
static long gcd(long a, long b)
{
return b==0 ? a : gcd( b, a%b);
}
static long lcm(long a, long b)
{
return (a*b)/gcd( a, b);
}
static class Pair {
public int x;
public int y;
public long z;
public Pair(int x, int y,long z) {
this.x = x;
this.y = y;
this.z =z;
}
}
static long modpow(long a,long n){
long res=1;
while(n!=0){
if ((n & 1) == 1){
res*=a;
res%=mod2;
n-=1;
}else{
a*=a;
a%=mod2;
n>>=1;
}
}
return res;
}
static void arraySort(int arr[]) {
ArrayList<Integer> a = new ArrayList<Integer>();
for (int i = 0; i < arr.length; i++) {
a.add(arr[i]);
}
Collections.sort(a);
for (int i = 0; i < arr.length; i++) {
arr[i] = a.get(i);
}
}
static class FastReader {
byte[] buf = new byte[2048];
int index, total;
InputStream in;
FastReader(InputStream is) {
in = is;
}
int scan() throws IOException {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0) {
return -1;
}
}
return buf[index++];
}
String next() throws IOException {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan()) {
sb.append((char) c);
}
return sb.toString();
}
int nextInt() throws IOException {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
long nextLong() throws IOException {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+') {
c = scan();
}
for (; c >= '0' && c <= '9'; c = scan()) {
val = (val << 3) + (val << 1) + (c & 15);
}
return neg ? -val : val;
}
int[] nextArrInt(int n) throws IOException {
int[] a = new int[n];
for (int i = 0; i < n; i++)
a[i] = nextInt();
return a;
}
long[] nextArrLong(int n) throws IOException {
long[] a = new long[n];
for (int i = 0; i < n; i++)
a[i] = nextLong();
return a;
}
}
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;
public Reader() {
din = new DataInputStream(System.in);
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public Reader(String file_name) throws IOException {
din = new DataInputStream(
new FileInputStream(file_name));
buffer = new byte[BUFFER_SIZE];
bufferPointer = bytesRead = 0;
}
public String readLine() throws IOException {
byte[] buf = new byte[64]; // line length
int cnt = 0, c;
while ((c = read()) != -1) {
if (c == '\n') {
if (cnt != 0) {
break;
} else {
continue;
}
}
buf[cnt++] = (byte) c;
}
return new String(buf, 0, cnt);
}
public int nextInt() throws IOException {
int ret = 0;
byte c = read();
while (c <= ' ') {
c = read();
}
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public long nextLong() throws IOException {
long ret = 0;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (neg)
return -ret;
return ret;
}
public double nextDouble() throws IOException {
double ret = 0, div = 1;
byte c = read();
while (c <= ' ')
c = read();
boolean neg = (c == '-');
if (neg)
c = read();
do {
ret = ret * 10 + c - '0';
} while ((c = read()) >= '0' && c <= '9');
if (c == '.') {
while ((c = read()) >= '0' && c <= '9') {
ret += (c - '0') / (div *= 10);
}
}
if (neg)
return -ret;
return ret;
}
private void fillBuffer() throws IOException {
bytesRead = din.read(buffer, bufferPointer = 0,
BUFFER_SIZE);
if (bytesRead == -1)
buffer[0] = -1;
}
private byte read() throws IOException {
if (bufferPointer == bytesRead)
fillBuffer();
return buffer[bufferPointer++];
}
public void close() throws IOException {
if (din == null)
return;
din.close();
}
public void printarray(int arr[]) {
for (int i = 0; i < arr.length; i++)
System.out.print(arr[i] + " ");
System.out.println();
}
}
}