Submission #781540

#	Time	Username	Problem	Language	Result	Execution time	Memory
781540		vjudge1	Sorting (IOI15_sorting)	C++17	100 / 100	153 ms	27396 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define K 600005
#define LOGN 20

int n, s[K], m, x[K], y[K], p[K], q[K];
vector<pii> swaps;

int check(int k){
	vector<int> res(n), ind(n);
    int todo = 0;
    for (int i = 0; i < n; i++)
    {
    	res[i] = s[i];
    	ind[s[i]] = i;
    }
   	swaps.clear();
    for (int i = 0; i < k; i++){
    	swap(res[x[i]], res[y[i]]);
    	ind[res[x[i]]] = x[i], ind[res[y[i]]] = y[i];
    }

    for (int i = 0; i < n; i++){
    	if (res[i] != i) {
    		int a = i, b = ind[i];
    		swaps.pb({res[i], i});
    		swap(res[a], res[b]);
    		ind[res[a]] = a, ind[res[b]] = b;
    	}
    }

    if (swaps.size() <= k) return 1;
    return 0;
}


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++)
    	x[i] = X[i], y[i] = Y[i];

 	int ans = 0;
 	for (int i = LOGN; i >= 0; i--){
 		int tmp = ans + (1<<i);
 		if (tmp <= m && check(tmp) == 0) ans = tmp;
 	}   

 	if (check(ans) == 0) ans++;
 	int tmp = check(ans);
 	vector<int> res(N), ind(N);
    int todo = 0;
    for (int i = 0; i < n; i++)
    {
    	res[i] = s[i];
    	ind[s[i]] = i;
    }
/*
    for (auto i : swaps){
    	cout<<i.st<<sp<<i.nd<<endl;
    }*/
    reverse(swaps.begin(), swaps.end());
 	for (int i = 0; i < ans; i++){
 		/*
 		for (auto i : res) cout<<i<<sp;
 		cout<<endl;*/
 		swap(res[X[i]], res[Y[i]]);
    	ind[res[X[i]]] = X[i], ind[res[Y[i]]] = Y[i];
    	if (swaps.empty()){
    		P[i] = 0, Q[i] = 0;
    	}
    	else{
    		int a = swaps.back().st, b = swaps.back().nd;
    		swaps.pop_back();
    		P[i] = ind[a], Q[i] = ind[b];
    		swap(res[P[i]], res[Q[i]]);
    		ind[res[P[i]]] = P[i], ind[res[Q[i]]] = Q[i];
    	}
 	}
 	return ans;
 }

Compilation message (stderr)

sorting.cpp: In function 'int check(int)':
sorting.cpp:39:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     if (swaps.size() <= k) return 1;
      |         ~~~~~~~~~~~~~^~~~
sorting.cpp:18:9: warning: unused variable 'todo' [-Wunused-variable]
   18 |     int todo = 0;
      |         ^~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   49 |     for (int i = 0; i < m; i++)
      |     ^~~
sorting.cpp:52:3: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   52 |   int ans = 0;
      |   ^~~
sorting.cpp:59:7: warning: unused variable 'tmp' [-Wunused-variable]
   59 |   int tmp = check(ans);
      |       ^~~
sorting.cpp:61:9: warning: unused variable 'todo' [-Wunused-variable]
   61 |     int todo = 0;
      |         ^~~~

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