Блог пользователя Akash_Roy

Автор Akash_Roy, история, 4 года назад, По-английски

This is the problem link

An O(n^2) solution gave me TLE on test 10. I came across one of the solutions below.

main() {

int n,i,f,s;
 cin>>n;
 map<int,int> mp;
 pair<int , int> a[n];
 for(i=0;i<n;i++)
 {
    cin>>f>>s;
    mp[f]++;
    a[i]={f,s};
 }

int m=n-1;
for(i=0;i<n;i++)
{
    a[i].first=m+mp[a[i].second];
    a[i].second=m-mp[a[i].second];

    cout<<a[i].first<<" "<<a[i].second<<endl;
}

}

I don't understand how the following two lines work.

a[i].first=m+mp[a[i].second];

a[i].second=m-mp[a[i].second];

Each team plays n-1 home and n-1 away games . But what is purpose of mp[a[i].second]? Please help.

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

mp[i] denotes the number of teams which have color i as their home kit. Then, mp[a[i].second] is the number of teams which have home kit being the same color as your away kit, or in other words, the number of games where you would normally play your away kit but have to play your home kit instead.

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Thanks Tzak. I got your point :)