Submission #223568

#	Time	Username	Problem	Language	Result	Execution time	Memory
223568		davitmarg	Sorting (IOI15_sorting)	C++17	20 / 100	90 ms	512 KiB

sorting

/*DavitMarg*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <list>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;
#ifndef death
	#include "sorting.h"
#endif
 
const int N = 200005;
 
int n,q,x[3*N],y[3*N];
vector<int> s,pos;
 
vector<pair<int,int>> solve(int r)
{
    vector<int> a=s,p(n),ind=pos;
    vector<pair<int,int>> ans;
 
    for(int i=0;i<r;i++)
        swap(a[x[i]],a[y[i]]);
 
    for(int i=0;i<n;i++)
		p[pos[a[i]]]=i;
	a=s;
    for(int i=0;i<n;i++)
	{
		//cout<<a[i]<<" ,";
		if(p[i]!=a[i])
		{
            ans.PB(MP(i,ind[p[i]]));
            swap(a[i],a[ind[p[i]]]);
			swap(ind[a[i]],ind[a[ind[p[i]]]]);
		}
		assert((p[i]==a[i]));
	}
 
	return ans;
}
 
int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[])
{
	n=N;
	for(int i=0;i<n;i++)
		s.PB(S[i]);
	pos=s;
	for(int i=0;i<n;i++)
		pos[s[i]]=i;
	q=M;
	for(int i=0;i<q;i++)
	{
		x[i]=X[i];
		y[i]=Y[i];
	}
    int l=0,r=n,m,pos=-1;
	vector<pair<int,int>> ans;
	/*while(l<=r)
	{
		m=(l+r)/2;
        if(solve(m).size()<=m)
		{
			pos=m;
			r=m-1;
		}
		else
			l=m+1;
	}*/
  	for(int i=n;i>=0;i--)
      if(solve(i).size()<=i)
        pos=i;
	assert(pos!=-1);
	ans=solve(pos);
	while(ans.size()<pos)
		ans.PB(MP(0,0));
	for(int j=0;j<ans.size();j++)
	{
		P[j]=ans[j].first;
		Q[j]=ans[j].second;
	}
 
	return pos;
}
 

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:63:70: warning: declaration of 'N' shadows a global declaration [-Wshadow]
 int findSwapPairs(int N,int S[],int M,int X[],int Y[],int P[],int Q[])
                                                                      ^
sorting.cpp:32:11: note: shadowed declaration is here
 const int N = 200005;
           ^
sorting.cpp:77:19: warning: declaration of 'pos' shadows a global declaration [-Wshadow]
     int l=0,r=n,m,pos=-1;
                   ^~~
sorting.cpp:35:15: note: shadowed declaration is here
 vector<int> s,pos;
               ^~~
sorting.cpp:91:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(solve(i).size()<=i)
          ~~~~~~~~~~~~~~~^~~
sorting.cpp:95:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(ans.size()<pos)
        ~~~~~~~~~~^~~~
sorting.cpp:97:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<ans.size();j++)
              ~^~~~~~~~~~~
sorting.cpp:77:9: warning: unused variable 'l' [-Wunused-variable]
     int l=0,r=n,m,pos=-1;
         ^
sorting.cpp:77:13: warning: unused variable 'r' [-Wunused-variable]
     int l=0,r=n,m,pos=-1;
             ^
sorting.cpp:77:17: warning: unused variable 'm' [-Wunused-variable]
     int l=0,r=n,m,pos=-1;
                 ^

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