rj_7's blog

Doubt
By rj_7, history, 5 years ago, In English

Question- Nastya is buying lunch 1136D

My approach for this question is similar to it's solution 1 of the editorial, but my submission is giving TLE. In my code, I focused only on the pupil who can let Natya swap with them. So I kept a track of their position and iterated on all of such pupil to see whether they can actually let Natya advance by advancing all pupil who are between them and Natya. I feel solution 1 to this problem is also similar but I don't know why my solution gives TLE. Also I don't get how the complexity of this solution is O(n+m).

Here is my code- ~~~~~

include

include

include

using namespace std;

int a[300000],b[500000]={0};

map<pair<int,int>,int> mymap;

map<int,int> pos;

void swap(int i,int j) { int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; }

int main() {

int n,m,x,y,j=0;

    cin>>n>>m;

    for(int i=0;i<n;i++)
{
    cin>>a[i];
}

    for(int i=0;i<m;i++)
{
    cin>>x>>y;
    mymap[{x,y}]=1;

}

    for(int i=0;i<n;i++)
{
    if(mymap[{a[i],a[n-1]}]==1)
    {
       b[j]=a[i];
       j++;
       pos[a[i]]=i;
    }
}
j--;
int nastya=a[n-1],i;
while(j>=0)
{
    for(i=pos[b[j]];a[i+1]!=nastya;i++)
    {
       if(mymap[{a[i],a[i+1]}]==1)
         swap(i,i+1);
       else
         break;
    }
    if(a[i+1]==nastya)
    {
       if(mymap[{a[i],a[i+1]}]==1)
         swap(i,i+1);
    }
    j--;
}
for(i=0;i<n;i++)
{
    if(a[i]==nastya)
       break;
}
cout<<n-1-i<<endl;

} ~~~~~

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Please ignore that bold 'includes'. I'm posting for first time and I tried to edit it but I couldn't do it.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +24 Vote: I do not like it

Tip for you, if you want to show your code to the community, try to upload somewhere(for example, ideone or pastebin) or just put these three ``` characters to the front and end of your entire code while writing to the blog, otherwise it is hard to read your code. For instance, here is your code:

Code
→ Reply