Show all threads Hide all threads Show all messages Hide all messages | WA5 Python | Shepeleva Elena | 1037. Memory Management | 21 Mar 2024 22:28 | 1 | 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)) | WA 4 | 👑TIMOFEY👑 | 1037. Memory Management | 1 Mar 2023 18:01 | 1 | WA 4 👑TIMOFEY👑 1 Mar 2023 18:01 dont forget return in your functions | Nice problem | guilty spark | 1037. Memory Management | 14 Aug 2021 21:17 | 2 | Similar to page scheduling. Used two sets to simulate the process. :) | Nice problem. | beastsl | 1037. Memory Management | 29 Aug 2018 22:24 | 1 | Done with queue + segment tree, AC in 0.265 on Visual C++ 2017 | hehe | 大笨象=o=喳支枪 | 1037. Memory Management | 13 May 2014 12:27 | 1 | hehe 大笨象=o=喳支枪 13 May 2014 12:27 | W5!!!WHY!!! | zsyzzsx2 | 1037. Memory Management | 3 Dec 2011 06:50 | 2 | 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... | Very strange behavior | Amirbekov Artem[Ivanovo SPU] | 1037. Memory Management | 22 Oct 2011 03:49 | 1 | 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 | lasha_kapo | 1037. Memory Management | 11 May 2011 13:10 | 2 | 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... | There is one useful test here | Burunduk1 | 1037. Memory Management | 12 Jan 2011 14:50 | 4 | 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~ | tle#7 | sbsbsb | 1037. Memory Management | 1 Jun 2010 00:07 | 1 | tle#7 sbsbsb 1 Jun 2010 00:07 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... | What's WA#4 | Gene JHZ | 1037. Memory Management | 31 Mar 2010 14:58 | 6 | 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 | What is the tricky part of this problem? Any hint please...WA on #4 | Danica Porobic | 1037. Memory Management | 7 Mar 2010 20:08 | 5 | 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 + | WA#1 | frp | 1037. Memory Management | 26 Feb 2010 21:27 | 1 | WA#1 frp 26 Feb 2010 21:27 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; } | TLE 7 | AiD | 1037. Memory Management | 7 Feb 2010 18:05 | 4 | TLE 7 AiD 25 Aug 2006 23:02 I have TLE on test 7. Why it can be? 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 :) | Long reading time | Ildar Valiev | 1037. Memory Management | 20 Mar 2009 23:58 | 6 | 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 | WA 7. What is the test #7? | Programmer | 1037. Memory Management | 7 Feb 2009 02:13 | 1 | | Help me!! Tell me how to improve my program ..I got TLE at test#5! | Ginforward | 1037. Memory Management | 14 Apr 2008 14:48 | 1 | 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. | Brute force WA#3 ??? | bsilver.info | 1037. Memory Management | 6 Mar 2008 13:54 | 1 | 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; }
| Crash @Test#3. If I use more than 16MB for this problem, will the Judge Status inform "Crash" ? | Đoàn Tuấn Anh | 1037. Memory Management | 7 Jan 2008 11:33 | 2 | 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 | WA in test 2 please please help me Alexandru Popa | Anupam Ghosh,Bengal Engg and Science University,Shibpur,India | 1037. Memory Management | 24 Sep 2007 14:15 | 1 | 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?? |
|
|