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.

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

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
-
+
-

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.

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?

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?

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?

Plz, help me.

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

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??