Submission #160713

#	Time	Username	Problem	Language	Result	Execution time	Memory
160713		davitmarg	Sorting (IOI15_sorting)	C++17	0 / 100	1060 ms	564 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;

vector<pair<int,int>> solve(int r)
{
    vector<int> a=s,p(n);
    vector<pair<int,int>> ans;
    for(int i=0;i<r;i++)
        swap(a[x[i]],a[y[i]]);
    for(int i=0;i<r;i++)
		p[a[i]]=i;
    for(int i=0;i<r;i++)
	{
        swap(p[a[x[i]]],p[a[y[i]]]);
        swap(a[x[i]],a[y[i]]);
		for(int k=0;k<n;k++)
			if(k!=p[a[k]])
			{
				ans.PB(MP(k,p[a[k]]));
				swap(k,p[a[k]]);
				break;
			}
	}
    for(int i=0;i<n;i++)
		if(a[i]!=i)
		{
			ans.clear();
			return ans;
		}
	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]);
	q=M;
	for(int i=0;i<q;i++)
	{
		x[i]=X[i];
		y[i]=Y[i];
	}
	for(int i=0;i<q;i++)
	{
		vector<pair<int,int>> ans=solve(i+1);
        if(!ans.empty())
		{
            for(int j=0;j<i;j++)
			{
				P[j]=ans[j].first;
				Q[j]=ans[j].second;
			}
			return ans.size()+1;
		}
	}


}


#ifdef death

int main()
{
    int N,S[102],M,X[102],Y[102],P[102],Q[102],R;
    cin>>N;
    for(int i=0;i<N;i++)
		cin>>S[i];
	cin>>M;
    for(int i=0;i<M;i++)
		cin>>X[i]>>Y[i];
	R=findSwapPairs(N,S,M,X,Y,P,Q);
	cout<<R<<endl;
	for(int i=0;i<R;i++)
		cout<<P[i]<<" : "<<Q[i]<<endl;
    return 0;
}

#endif

/*

5
3 0 4 2 1
5
1 1
4 0
2 3
1 4
0 4


*/

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66: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:87:21: warning: conversion to 'int' from 'std::vector<std::pair<int, int> >::size_type {aka long unsigned int}' may alter its value [-Wconversion]
    return ans.size()+1;
           ~~~~~~~~~~^~
sorting.cpp:92:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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