Submission #415276

#	Time	Username	Problem	Language	Result	Execution time	Memory
415276		TLP39	Sorting (IOI15_sorting)	C++14	100 / 100	163 ms	26804 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pp;

int n,m;
int state=0;
int pos[200010];
int s[200010];
int sw[600010][2];
bool ch[200010];
int ans;
vector<pp> pq;

void swaps(int p1,int p2)
{
    int temp=s[p1];
    s[p1]=s[p2];
    s[p2]=temp;
}

void change_to_state(int st)
{
    while(state<st)
    {
        state++;
        swaps(sw[state][0],sw[state][1]);
    }
    while(state>st)
    {
        swaps(sw[state][0],sw[state][1]);
        state--;
    }
}

int count_cycle()
{
    for(int i=0;i<n;i++) ch[i]=false;
    int cycle_num=0,cur;
    for(int i=0;i<n;i++)
    {
        if(ch[i]) continue;
        cycle_num++;
        ch[i]=true;
        cur=s[i];
        while(cur!=i)
        {
            ch[cur]=true;
            cur=s[cur];
        }
    }
    return cycle_num;
}

void find_ans()
{
    int hi=m,low=0,av;
    while(hi>low)
    {
        av=(hi+low)>>1;
        change_to_state(av);
        if(count_cycle()+av>=n) hi=av;
        else low=av+1;
    }
    ans=hi;
    return;
}

void get_pq()
{
    change_to_state(ans);
    for(int i=0;i<n;i++)
    {
        while(s[i]!=i)
        {
            pq.push_back({i,s[i]});
            swaps(i,s[i]);
        }
    }
    while(pq.size()<ans)
    {
        pq.push_back({1,1});
    }
}

void change_pq()
{
    for(int i=0;i<n;i++) pos[i]=i;
    int temp;
    for(int i=ans-2;i>=0;i--)
    {
        swaps(pos[sw[i+2][0]],pos[sw[i+2][1]]);
        temp=pos[sw[i+2][0]];
        pos[sw[i+2][0]]=pos[sw[i+2][1]];
        pos[sw[i+2][1]]=temp;
        pq[i]={s[pq[i].first],s[pq[i].second]};
    }
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    n=N;
    m=M;
    for(int i=0;i<n;i++)
    {
        s[i]=S[i];
    }
    for(int i=0;i<m;i++)
    {
        sw[i+1][0]=X[i];
        sw[i+1][1]=Y[i];
    }
    find_ans();
    get_pq();
    change_pq();
    for(int i=0;i<ans;i++)
    {
        P[i]=pq[i].first;
        Q[i]=pq[i].second;
    }
	return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'void get_pq()':
sorting.cpp:80:20: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   80 |     while(pq.size()<ans)
      |           ~~~~~~~~~^~~~

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 16 / 16
• Subtask 4: 18 / 18
• Subtask 5: 20 / 20
• Subtask 6: 26 / 26