ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1439. Battle with You-Know-Who

WHY WA#2?
Posted by Aleksander 10 Jul 2008 13:21
This is my program
program preg;
var n,m,i,t,ch,e,sh,k,shh:longint;st:boolean;s:string;des,otv:array[1..100000]of longint;b:array[1..100000]of boolean;
begin
sh:=1;
for i:=1 to m do begin
if (s[1]='L') then b[sh]:=true
else b[sh]:=false;
val(s[3],ch,e);
des[sh]:=ch;sh:=sh+1;
end;
sh:=1;
for i:=2 to m+1 do begin
if b[i-1]=false then begin
for k:=i to m do begin
if des[k]>=des[i-1]then begin
shh:=0;st:=false;
while st=false do begin
shh:=shh+1;st:=true;
for t:=1 to i-1 do begin
if (des[k]+shh=des[t])and(b[t]=false)then st:=false;
end;
end;
des[k]:=des[k]+shh;
end;
end;
end;
if b[i-1]=true then begin
otv[sh]:=des[i-1];sh:=sh+1;
end;
end;
for i:=1 to sh-1 do writeln(otv[i]);
end.
Re: WHY WA#2?
Posted by xurshid_n 25 Aug 2009 19:52
I use balanse tree, but WA#2. here my code.
What is test#2?

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

public class Problem_1439 implements Runnable{
public static void main(String []args){
}
public void run(){
try{
solve();
}catch(IOException e){
throw new IllegalStateException(e);
}
}

int nextInt()throws IOException{
}

boolean nextType()throws IOException{
if (s.length()!=1 && s.charAt(0)!='L' && s.charAt(0)!='D'){
for (int i = 0; i< 100000000;i++)System.out.println("ERORO");
}
}

int n, m;

final int MAX_N = 111111;

class node{
int left, right;
int lleft, rright;
int x, y;
int size;

node(){
left = right= x = y = size =  lleft = rright = 0;
}
}
node tree[];
int g[];
int  lt, root;
int i, j, c, k;
int getSize(int root){
return (root == 0 ) ? 0: tree[root].size;
}

int insert(int root, int x, int y){
if (root == 0 || tree[root].y <= y){

lt++;
//tree[lt] = new node();
tree[lt].left   = 0;
tree[lt].right  = 0;
tree[lt].lleft  = lt;
tree[lt].rright = lt;
tree[lt].x = x;
tree[lt].y = y;

if (root > 0){
if (tree[root].x < x)tree[lt].left = root; else tree[lt].right = root;
}
tree[lt].size = 1 + getSize(tree[lt].left)+getSize(tree[lt].right);
if (tree[lt].left > 0)tree[lt].lleft = tree[tree[lt].left].lleft;
if (tree[lt].right > 0)tree[lt].rright = tree[tree[lt].right].rright;
return lt;
}else if (x > tree[root].x){
tree[root].size ++;
tree[root].right = insert(tree[root].right, x, y);
tree[root].rright = tree[tree[root].right].rright;
return root;
}else {
tree[root].size++;
tree[root].left = insert(tree[root].left, x, y);
tree[root].lleft = tree[tree[root].left].lleft;
return root;
}
}
int getId(int root, int k, int min){
if (root == 0)return k + min;
int sz = getSize(tree[root].left);
int delta = tree[root].x - (min + sz + 1);
//if (delta < k)return getId(tree[root].right, k, min + sz + 1);
if (delta >= k){
if (tree[root].left == 0)return k + min;
int lright = tree[tree[root].left].rright;
int delta2 = tree[lright].x - (min  + sz);
if (delta2 < k)return k + min + sz;else return getId(tree[root].left, k, min);
}else {
if (tree[root].right == 0)return k + min + sz + 1;
int rleft = tree[tree[root].right].lleft;
int delta2 = tree[rleft].x - (min + sz + 2);
if (delta2 >= k)return k + min + sz + 1; else return getId(tree[root].right, k , min + sz + 1);
}
}

void solve()throws IOException{
n = nextInt();
m = nextInt();
g = new int[ MAX_N+1];
tree = new node[MAX_N + 1];
for (i = 0; i<=MAX_N;i++){
tree[i] = new node();

}
Random random = new Random();
for (i = 1; i<=n;i++){
k = 1 + random.nextInt(i);
g[i] = g[k];
g[k] = i;
}
root = 0;
lt = 0;
j = 0;
int mind = n, maxd = 1, d = 0;
boolean type;
for (i = 1; i<= m;i++){
type = nextType();
k = nextInt();
k  = getId(root, k, 0);

if ( type ) {//L
System.out.println(k);
}else{//D
j++;
root = insert(root, k, g[j]);

}

}

}
}