|
|
back to boardWHY WA#2? 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? 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]);
}
}
} } |
|
|