Submission #223560

#	Time	Username	Problem	Language	Result	Execution time	Memory
223560		davitmarg	Sorting (IOI15_sorting)	C++17	0 / 100	11 ms	640 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, a[N], b[N], s[N], x[3 * N], y[3 * N];
int pos[N], posa[N];
vector<pair<int, int>> ans;

bool check(int k)
{
	ans.clear();
	for (int i = 0; i < n; i++)
		a[i] = i;
	for (int i = 0; i < k; i++)
		swap(a[x[i]], a[y[i]]);
	for (int i = 0; i < n; i++)
	{
		posa[a[i]] = i;
		pos[s[i]] = a[i];
		b[a[i]] = s[i];
	}
	for (int i = 0; i < n; i++)
	{
		if (b[i] == i)
			continue;
		//swap pos[b[i]] pos[i];
		int x= pos[b[i]], y=pos[i];
		ans.push_back(MP(posa[pos[b[i]]], posa[pos[i]]));
		swap(b[x], b[y]);
	}
	while (ans.size() < k)
		ans.PB(MP(0, 0));
	return(ans.size() <= k);
	
}

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[i] = S[i];
	q = M;
	for (int i = 0; i < q; i++)
	{
		x[i] = X[i];
		y[i] = Y[i];
	}

	int l=0, r=n-1, m, c;
	while (l <= r)
	{
		m = (l + r) / 2;
		if (check(m))
		{
			c = m;
			r = m - 1;
		}
		else
			l = m + 1;
	}
	check(c);
	for (int i = 0; i < ans.size(); i++)
	{
		P[i] = ans[i].first;
		Q[i] = ans[i].second;
	}
	return ans.size();
}


#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 << endl;
	cout << R << endl;
	for (int i = 0; i < R; i++)
		cout << P[i] << " : " << Q[i] << endl;
	for (int i = 0; i < R; i++)
	{
		swap(S[P[i]], S[Q[i]]);
		swap(S[X[i]], S[Y[i]]);
	}
	for (int i = 0; i < N; i++)
		cout << S[i] << ", ";
	cout << endl;
	return 0;
}

#endif
/*

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

3
0 2 1
3
0 1
0 1
0 1

*/

Compilation message (stderr)

sorting.cpp: In function 'bool check(int)':
sorting.cpp:56:7: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   int x= pos[b[i]], y=pos[i];
       ^
sorting.cpp:34:29: note: shadowed declaration is here
 int n, q, a[N], b[N], s[N], x[3 * N], y[3 * N];
                             ^
sorting.cpp:56:21: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   int x= pos[b[i]], y=pos[i];
                     ^
sorting.cpp:34:39: note: shadowed declaration is here
 int n, q, a[N], b[N], s[N], x[3 * N], y[3 * N];
                                       ^
sorting.cpp:60:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while (ans.size() < k)
         ~~~~~~~~~~~^~~
sorting.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return(ans.size() <= k);
         ~~~~~~~~~~~^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:66:76: 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:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < ans.size(); i++)
                  ~~^~~~~~~~~~~~
sorting.cpp:96:17: 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();
         ~~~~~~~~^~
sorting.cpp:90:7: warning: 'c' may be used uninitialized in this function [-Wmaybe-uninitialized]
  check(c);
  ~~~~~^~~

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