class MemoryManager: def __init__(self, n, t): self.n = n self.t = t self.blocks = {} self.free_blocks = set(range(1, n + 1)) def allocate_block(self, time): block = min(self.free_blocks) self.free_blocks.remove(block) self.blocks[block] = time + self.t return block def access_block(self, time, block_no): if block_no in self.blocks and self.blocks[block_no] >= time: return '+' else: return '-' n = 30000 t = 10 memory_manager = MemoryManager(n, t) queries = input().strip() for query in queries: query_type = query[0] time = query[1] if query_type == '+': print(memory_manager.allocate_block(time)) elif query_type == '.': block_no = query[2] print(memory_manager.access_block(time, block_no)) dont forget return in your functions Similar to page scheduling. Used two sets to simulate the process. :) Done with queue + segment tree, AC in 0.265 on Visual C++ 2017 var ncb:array[1..30000]of boolean; nct:array[1..30000]of longint; i,j,k,n,t:longint; c:char; begin repeat read(t,c);read(c); if c='.' then begin readln(n); if ncb[n] then begin if t-nct[n]<600 then begin writeln('+'); nct[n]:=t; end else writeln('-'); end else writeln('-'); end else begin i:=1; while (t-nct[i]<600) and (ncb[i]=true) do inc(i); ncb[i]:=true; nct[i]:=t; writeln(i); end; until eof; end. there is 30001 number of box in this case... The first time I had submitted my solution I got WA 1 After I changed the main line where first number and symbol are read from while (scanf("%d %s", &time, &s) != EOF) to: while (cin >> time >> s) I got AC. What's the difference? Tell Me Solution Use queue. Store top-time in each queue element Before each operation check died elements and remove it from queue. Put processed element into end of queue To speed up searching of free element, you can store in some variable index of least element that can be empty. When you allocating next element, you increase it. When one elemenet if "dying" with index less than that stored value, you assign to that index of died element. And so on and so on... It helped me to get AC. Test: 1 + 1 + 1 + 10 . 2 11 . 3 600 + 601 . 1 609 . 2 611 . 3 Right answer: 1 2 3 + + 4 - + - this is giving correct output for me but i am failing in test case 2 why ? can u help this is giving correct output for me but i am failing in test case 2 why ? can u help Thank you very much! I can't get AC without it,either~ I've tried the heap one, I've done everything I could, but still TLE. I guess there should be some tricky part or my implementation error. what have you guys done to avoid the TLE? I use heap to arrange the time, everytime there is a new timestamp that is different from the last one, I check the heap and delete the out-of-time nodes. I also use a bool array to record the existance of a node, as well as a link table to record the next label that can be used. I don't know why I got TLE all the time... Can any one help me? I got WA#4. But I have no idea where I made a mistake. I need some tests. I might ignored something important. Thanks. Test: 0 + 0 + 2 . 1 ------ Answer: 1 2 + I think you assumed that it starts working from time = 1 s. :) I've checked this case and still get WA at 4. Here is the 4th test : Input : 0 . 16 1 . 10 27 . 35 74 . 22 79 + 107 . 8 147 + 185 + 232 . 21 279 + 325 + 347 + 380 + 407 + 412 . 6 445 . 24 473 . 43 486 . 21 520 . 26 552 + 552 + 565 . 19 583 + 613 . 8 653 . 16 673 . 20 675 . 49 675 . 3 678 . 48 695 . 9 704 . 12 741 + 786 + 809 + 810 . 22 834 + 846 . 35 878 + 921 . 27 946 + 984 . 10 995 . 28 1001 + 1002 + 1012 + 1043 + 1079 + 1107 . 16 1150 + 1180 + 1229 + 1265 + 1279 + 1293 + 1317 . 27 1336 + 1355 + 1361 . 16 1406 + 1438 + 1470 + 1506 + 1527 + 1545 + 1545 + 1567 . 27 1591 + 1626 + 1665 . 2000 1706 + 1755 . 17 1801 + 1829 + 1840 . 44 1843 + 1873 . 42 1909 + 1955 . 14 1989 . 17 2026 + 2072 . 20 2117 . 16 2161 . 7 2177 . 31 2224 . 5 2272 . 10 2276 + 2319 + 2332 + 2376 + 2380 + 2421 + 2457 + 2484 + 2533 . 18 2569 . 34 2585 . 18 2597 + 2598 + 2598 . 12 Correct output : - - - - 1 - 2 3 - 4 5 6 7 8 + - - - - 9 10 - 11 + - - - + - + - 1 2 12 - 13 - 14 - 4 + - 5 7 6 15 16 + 17 18 8 11 3 19 - 9 1 + 2 12 13 14 20 21 22 - 4 5 - 6 - 7 8 - 10 - 3 + - 1 + - + - + + 2 4 6 9 11 12 8 13 - - - 3 14 + Good luck . my soln is exactly equal to what u have posted. but failing in test 2. any reason?? please help I've tried to solve this problem, using simple aproach, only one array in which i remember time until that part of the memory is allocated. On request I check if it's used, if is shift time to new value if not nothing change... On new allocation I search for the first free memory spot... Very simple, straight from the text, but I get WA on #4. Could someone post some tricky test or explain why my algorithm is wrong? Thank you very much! I wouldn't say that it was very easy, but I got AC and learn new way of programming. Try this test: 64999 + 65000 . 1 --------- 1 + I got WA#1. But my program gives correct result for all tests what i found on this forum. Why WA#1? Please give tests where my program will give incorrect result. My source code: //////////////////////////// ///Stupid brute force #include <iostream> #include <cstdio> using namespace std; int mem[30000]; //set<int> fb; int main() { char a[100]; char c; int ltd=0; int i; for(i=0;i<30000;i++)mem[i]=0; while(!cin.eof()) { cin.getline(a,100); int t,mp; sscanf(a,"%d %c%d",&t,&c,&mp); mp--; int mfb=40000; for(i=0;i<30000;i++) { mem[i]-=t-ltd; if((mem[i]<1)&&(i<mfb)){mfb=i;if(t==ltd)break;} } if(c=='+') { mem[mfb]=600; cout<<mfb+1<<'\n'; } else { if(mem[mp]>0){mem[mp]=600;cout<<"+\n";} else cout<<"-\n"; } ltd=t; } return 0; } I have TLE on test 7. Why it can be? Me too~~~~~~ Requests with equal times should be processed as they appear in input !!! TLE 7 is probably like this 1+ 1+ 1+ 1+ 1+ 1+ ... ... ... ... Edited by author 15.08.2008 02:14 Thanks for your hint (about requests with equal times), i've got AC now :) Functions "scanf" and "cin" in C++ read data to long. For example, 100 KB of data readed be my prog in 2-3 seconds. But on last test, there are more than 400 KB of data. And now, question: Is in C++ any function, that read data faster? You're, possibly, joking =) scanf() reads data pretty fast - I rarely met problems in which you need to use faster techniques to input data. Maybe, your processing part of the program is too slow? No, I'm not joking) Even if I delete all proccesing part (leave only stream reading) all text will be readed about 2-3 seconds for 100 KB text. Or, may be, stream readed fast, but writing to console is too low? Sorry, for my English =) you are wrong #include <stdio.h> #include <stdlib.h> #include <ctime> using namespace std; int main() { int tm = clock(); FILE *f = fopen("out.txt", "w"); srand(0); int N = 100000; for (int i = 0; i < N; i++) { int x = rand(); fprintf(f, "%d\n", x); } freopen("out.txt", "r", stdin); printf("Write Time in seconds = %0.5lf\n", (clock() - tm) * 0.001); tm = clock(); int sum = 0; for (int i = 0; i < N; i++) { int x; scanf("%d", &x); sum += x; } printf("Read Time in seconds = %0.5lf\n", (clock() - tm) * 0.001); printf("%d\n", sum); return 0; } size of file is 650kb, and time is 0.125 for writing, and 0.062 for reading on my slow computer Edited by author 20.03.2009 21:18 Alias, thanks. I'll think how to make my solution faster. :) I'm try to do same just now, and get this result: Time, needed for reading from CONSOLE (not from file) is 5.628 sec for 650 KB. Here is me prog: #include "stdio.h" #include "ctime" int main() { char c; scanf("%c", &c); int tm = clock(); while (scanf("%c", &c) != EOF) {} printf ("%0.5lf", (clock()-tm)*0.001); return 0; } Edited by author 21.03.2009 11:26 Edited by author 21.03.2009 11:26 program ural1037; type tt=record lch,rch,cover,till1,a,b:longint; end; var tree:array[1..60002]of tt; ans,nt,nb,tot,i,j,k,now:longint; s:string; flag:boolean; procedure maketree(l,r:longint); var now:longint; begin inc(tot); now:=tot; tree[now].a:=l; tree[now].b:=r; tree[now].till1:=-1; if l<r then begin tree[now].lch:=tot+1; maketree(l,(l+r)shr 1); tree[now].rch:=tot+1; maketree((l+r)shr 1 +1,r); end; end; procedure coverit(now:longint); function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin if (tree[now].a=tree[now].b)and(tree[now].a<>0)and((tree[now].cover=0) or(tree[now].till1<nt)) then begin tree[now].cover:=1; tree[now].till1:=nt+599; ans:=tree[now].a; end; if tree[now].a<>tree[now].b then begin if ans=-1 then coverit(tree[now].lch); if ans=-1 then coverit(tree[now].rch); if tree[now].a<tree[now].b then begin tree[now].till1:=max(tree[tree[now].lch].till1,tree[tree[now].rch].till1); if (tree[tree[now].lch].cover=1)and(tree[tree[now].rch].cover=1) then tree[now].cover:=1; end; end; end; procedure checkit(now:longint); var mid:longint; function max(x,y:longint):longint; begin if x>y then exit(x) else exit(y); end; begin mid:=(tree[now].a+tree[now].b)shr 1; if tree[now].till1<nt then exit else if (tree[now].a=tree[now].b)and (tree[now].till1>=nt) then begin tree[now].till1:=nt+599; flag:=true; exit; end else begin if nb<=mid then checkit(tree[now].lch) else checkit(tree[now].rch); if tree[now].a<tree[now].b then tree[now].till1:=max(tree[tree[now].lch].till1,tree[tree[now].rch].till1); end; end; begin tot:=0; maketree(0,30000); while not eof do begin readln(s); if pos('+',s)<>0 then begin val(copy(s,1,pos(' ',s)-1),nt); ans:=-1; coverit(1); writeln(ans); end else if pos('.',s)<>0 then begin val(copy(s,1,pos(' ',s)-1),nt); delete(s,1,pos('.',s)+1); val(s,nb); flag:=false; checkit(1); if flag then writeln('+') else writeln('-'); end; end; end. Why do I get WA on test #3 ? I'm using a simple algorithm which stores the last time a lock was requested in a vector a[]. for the access request it checks whether the memory block #i has a request more recent than 600s. if yes it writes '+' and changes the last request time else it writes -. for the allocation request it searches for the first memory block that hasn't been accessed for at least 600s, writes it's number and changes the last request time. initially all memory blocks have a last reuest time of -601s so they are all free. i tried changing the input and output method a lot of times (for some problems it works) and checked my program several times with test in this discussion forum and of my own and the program gives the right answers. can someone fin where i'm wrong? why do i get WA? i think i should have got TLE for the worst of cases because the algorithm is kind of slow, but not WA. also here is the source code for my program: #include <stdio.h> long int a[30002]; int main(void) { long int i,timp; char c,buf; for(i=0;i<=30000;i++) a[i]=-601; scanf("%ld %c",&timp,&c); if(c=='.') scanf("%ld",&i); while(!feof(stdin)) { if(c=='.') { if(((timp-a[i]))<600) { a[i]=timp; printf("+\n"); } else printf("-\n"); } else if(c=='+') { for(i=1;(((timp-a[i]))<600);i++); printf("%ld\n",i); a[i]=timp; } scanf("%ld %c",&timp,&c); if(feof(stdin)) return 0; if(c=='.') scanf("%ld",&i); } return 0; }
Can anyone give me test#3 or explain what is the meaning of "Crash" in Java ? Thanks Never mind. Get AC now. After a series of TLE-> Crash -> Wrong Answer -> MLE -> TLE -> AC :D can any body help me to clear test 2 .i think Alexandru Popa had faced similar difficulties can u please help me with a test case?? |
|