### rj_7's blog

By rj_7, history, 5 months ago, ,

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

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;

} ~~~~~

• +14

 » 5 months ago, # |   +11 Please ignore that bold 'includes'. I'm posting for first time and I tried to edit it but I couldn't do it.
 » 5 months ago, # | ← Rev. 3 →   +24 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`#include using namespace std; int a[300000],b[500000]={0}; map,int> mymap; map 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>a[i]; } for(int i=0;i>x>>y; mymap[{x,y}]=1; } for(int i=0;i=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