ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
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
read(n);readln(m);
sh:=1;
for i:=1 to m do begin
readln(s);
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){
        new Thread(new Problem_1439()).start();
    }
    public void run(){
        try{
            reader = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
            solve();
        }catch(IOException e){
            throw new IllegalStateException(e);
        }
    }

    int nextInt()throws IOException{
        reader.nextToken();
        return (int)reader.nval;
    }

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

    int n, m;

    StreamTokenizer reader;

    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]);



            }

        }

    }
}