Luogu p1309 Swiss wheel

Take notes again
Topic link ：https://www.luogu.com.cn/problem/P1309

Title Description
2×N The name number is 1∼2N All of the contestants have R round . Before the start of each round , And after all the Games , Will be in accordance with the total score from high to low on a player ranking . The total score of a player is the initial score before the first round plus the scores of all competitions he has participated in and . The total score is the same , The player with the smaller number is in the top of the list .

The match arrangement of each round is related to the ranking before the start of the round ： The first 1 Name and number 2 name 、 The first 3 Name and number 4 name 、……、 The first 2K−1 Name and number 2K name 、…… 、 The first 2N−1 Name and number 2N name , One game each . The winner of every game gets 1 branch , The loser is the winner 0 branch . That is to say, in addition to the first round , The arrangement of other rounds can't be determined in advance , It depends on the player's performance in the previous competition .

Now give each player's initial score and strength value , Try to calculate in R After the round , Ranking the first QQ What's the player number of . Let's assume that the strength values of the players are different , And in every game, the one with higher strength always wins .
sample input
2 4 2
7 6 6 7
10 5 20 15
sample output
1
explain ：

** After reading this topic emm To understand it roughly is ： First of all, there is 2*n A contestant , To carry out r round , We want to output the ranking after the game q People who Each player has his own strength , Initial integral , Number （ You have to use a structure ） The order of the game is to let the first play the second , Third, fourth … Yes, of course , Of course, the ranking should be updated after the change of points after each competition （ This has to be sorted every time ？） **

Then look at the data range and time limit , Glancing at the time ,0.5s Ah, there are trees ！ This is a bit of a mess
It's impossible to directly simulate the fast line after every game
Think about where our direct sorting is slow , The winner of the game will add one point , Failure does not change , If someone was in front of you , You both win or both lose , Isn't he still in front of you ？
so ga！ But what's the use of that ？
This seems to mean that if we put the winners in a group , Fail to put a group , Then these two groups are still in order ！！ In fact, what we need to do is to combine two arrays that are already ordered ！
Hoarse This is the idea of merging and sorting
Let's start with the main idea

#include <bits/stdc++.h>
using namespace std;
#define N 3000000
int n,r,q;
struct player
{
    
    int num;
    int able;
    int score;
} a[N],win[N],lose[N];
int main()
{
    
    cin>>n>>r>>q;
    for(int i=1; i<=2*n; i++)a[i].num=i; // Number initialization 

    for(int i=1; i<=2*n; i++)scanf("%d",&a[i].score);
    for(int i=1; i<=2*n; i++)scanf("%d",&a[i].able); // Read in the data 

    sort(a+1,a+1+2*n,cmp);// Initialize the ranking before the game 

    while(r--)// Simulation Competition 
    {
    
        for(int i=1; i<=n; i++)
        {
    
            if(a[2*i-1].able>a[2*i].able)// Compare according to strength 
            {
    
                a[2*i-1].score++;
                win[i]=a[2*i-1];// Winners and losers are stored separately to ensure order 
                lose[i]=a[2*i];
            }
            else// There was no draw in the game 
            {
    
                a[2*i].score++;
                win[i]=a[2*i];
                lose[i]=a[2*i-1];
            }
        }
        my_merge();// Handwriting merge Function to merge winners and losers 
    }
    cout<<a[q].num<<endl;
    return 0;
}

There are two functions used One cmp Comparison function , Yeah , You make people sort You have to give a sorting standard to arrange the structure

int cmp(player x,player y)// Comparison function 
{
    
    if(x.score!=y.score)return x.score>y.score;
    else return x.num<y.num;// If the scores are the same, the number of small ones is in front 
}

This is easy to say , Points are in front of many rows , The same is better than the number , In front of the number row

There's another one my_merge Function? , To put two arrays win,lose Synthesis of a a
If this function doesn't work well, Barbie Q 了 , I have this card wa Half an hour , card tle I didn't know what happened to the kidney until I read other people's solutions for half an hour
Synthesis , Simple , acutely Go straight up

void my_merge()
{
    
    int k=0,i,j;
    i=j=1;
    while(k<2*n)
    {
    
        if(win[i].score>lose[j].score)
        {
    
            a[++k]=win[i];
            i++;
        }
        else if(win[i].score<lose[j].score)
        {
    
            a[++k]=lose[j];
            j++;
        }
        else// Compare numbers with the same scores 
        {
    
            if(win[i].num<lose[j].num)
            {
    
                a[++k]=win[i];
                i++;
            }
            else// The contestant number is unique 
            {
    
                a[++k]=lose[j];
                j++;
            }
        }
    }
}

The cyclic condition is a The array is full Then according to the comparison standard from win and lose Choose from the inside , Submit ！！

Listen to wa A sound. Is dubious
In this way, we ignore a problem In comparison win[i] lose[j] It doesn't have to be , You put it one by one In case win Everything inside has gone in i still ＋, Then no md fuck*running time error 了 （ However, I'm used to the fact that if the array is opened a little larger, it won't cross the boundary ） The answer is wrong
well Change ！

void my_merge()
{
    
    int k=0,i,j;
    i=j=1;
    while(k<2*n)
    {
    
        while(cmp(win[i],lose[j])&&i<=n)
        {
    
            a[++k]=win[i];
            i++;
        }
        while(cmp(lose[j],win[i])&&j<=n)
        {
    
            a[++k]=lose[j];
            j++;
        }
    }
}

Hey I changed it directly to while loop i If it is greater than n You can't get in That's not only j 了 Tact as I It's too early to be happy

This is a special change tle ah Or five points It's better not to change !
Don't be impatient. Don't be impatient What 0.5s Really?
Try fast reading ？

inline int qread(){
    
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
    
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
    
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

But it is of no damn use .. I want to know The amount of data read into this topic is not large , Adding a quick read doesn't work at all
Of course, if the data is big, fast reading is still very delicious
Then I ran to see others' solutions
After modification

void my_merge()
{
    
    int k=0,i,j;
    i=j=1;
    while(k<2*n)
    {
    
        if(i>n)
        {
    
            while(j<=n)
            {
    
                a[++k]=lose[j];
                j++;
            }
            break;
        }
        if(j>n)
        {
    
            while(i<=n)
            {
    
                a[++k]=win[i];
                i++;
            }
            break;
        }
        if(win[i].score>lose[j].score)
        {
    
            a[++k]=win[i];
            i++;
        }
        else if(win[i].score<lose[j].score)
        {
    
            a[++k]=lose[j];
            j++;
        }
        else// Compare numbers with the same scores 
        {
    
            if(win[i].num<lose[j].num)
            {
    
                a[++k]=win[i];
                i++;
            }
            else// The contestant number is unique 
            {
    
                a[++k]=lose[j];
                j++;
            }
        }
    }
}

In fact, it's just adding if Special judgement But I didn't figure out why I was so slow
Complete code （ There is also a debugging code ）

#include <bits/stdc++.h>
using namespace std;
#define N 3000000
int n,r,q;
struct player
{
    
    int num;
    int able;
    int score;
} a[N],win[N],lose[N];
int cmp(player x,player y)// Comparison function 
{
    
    if(x.score!=y.score)return x.score>y.score;
    else return x.num<y.num;// If the scores are the same, the number of small ones is in front 
}
void my_merge()
{
    
    int k=0,i,j;
    i=j=1;
    while(k<2*n)
    {
    
        if(i>n)
        {
    
            while(j<=n)
            {
    
                a[++k]=lose[j];
                j++;
            }
            break;
        }
        if(j>n)
        {
    
            while(i<=n)
            {
    
                a[++k]=win[i];
                i++;
            }
            break;
        }
        if(win[i].score>lose[j].score)
        {
    
            a[++k]=win[i];
            i++;
        }
        else if(win[i].score<lose[j].score)
        {
    
            a[++k]=lose[j];
            j++;
        }
        else// Compare numbers with the same scores 
        {
    
            if(win[i].num<lose[j].num)
            {
    
                a[++k]=win[i];
                i++;
            }
            else// The contestant number is unique 
            {
    
                a[++k]=lose[j];
                j++;
            }
        }
    }
}
/*void debug() { printf(" At present, the points of each player are ranked as follows ：\n Number   integral   power \n"); for(int i=1; i<=2*n; i++) { printf("%d %d %d\n",a[i].num,a[i].score,a[i].able); } }*/
int main()
{
    
    cin>>n>>r>>q;
    for(int i=1; i<=2*n; i++)a[i].num=i; // Number initialization 

    for(int i=1; i<=2*n; i++)scanf("%d",&a[i].score);
    for(int i=1; i<=2*n; i++)scanf("%d",&a[i].able); // Read in the data 

    sort(a+1,a+1+2*n,cmp);// Initialize the ranking before the game 

    while(r--)// Simulation Competition 
    {
    
        for(int i=1; i<=n; i++)
        {
    
            if(a[2*i-1].able>a[2*i].able)// Compare according to strength 
            {
    
                a[2*i-1].score++;
                win[i]=a[2*i-1];// Winners and losers are stored separately to ensure order 
                lose[i]=a[2*i];
            }
            else// There was no draw in the game 
            {
    
                a[2*i].score++;
                win[i]=a[2*i];
                lose[i]=a[2*i-1];
            }
        }
        my_merge();// Handwriting merge Function to merge winners and losers 
    }
    cout<<a[q].num<<endl;
    return 0;
}

Let out a sigh
The notes are written here
I wrote Luo Gu and roast by the way codefore This website The question is really difficult Slow reaction , You have to jump in a daze everywhere