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,b={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;

} ~~~~~ help, Comments (2)
 » 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 →   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,b={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