Submission #432991

#	Time	Username	Problem	Language	Result	Execution time	Memory
432991		wiwiho	Sorting (IOI15_sorting)	C++14	100 / 100	428 ms	19728 KiB

sorting

#include "sorting.h"
 
#include <bits/stdc++.h>
 
#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define Sc second
#define eb emplace_back
 
using namespace std;
 
typedef long long ll;
 
using pii = pair<int, int>;
 
const ll MOD = 1000000007;

vector<pii> ans;
bool calc(int n, int S[], int m, int X[], int Y[]){
    ans.clear();

    vector<int> s(n);
    for(int i = 0; i < n; i++) s[i] = S[i];
 
    vector<int> num(n);
    vector<int> pos(n);
    for(int i = 0; i < n; i++) num[i] = pos[i] = i;
    for(int i = 0; i < m; i++){
        swap(num[pos[X[i]]], num[pos[Y[i]]]);
        swap(pos[X[i]], pos[Y[i]]);
    }
 
    int cnt = 0;
    vector<int> now(n), np(n);
    for(int i = 0; i < n; i++) now[i] = i, np[i] = i;
    for(int i = 0; i < n; i++){
        while(s[i] != num[i]){
            if(cnt >= m) return false;
            swap(now[np[X[cnt]]], now[np[Y[cnt]]]);
            swap(np[X[cnt]], np[Y[cnt]]);
            cnt++;
            ans.eb(mp(now[i], now[pos[s[i]]]));
            swap(s[i], s[pos[s[i]]]);
        }
    }
    while(ans.size() < m) ans.eb(mp(0, 0));
    //cerr << "test " << m << "\n";
    //printv(num, cerr);
    //printv(s, cerr);
    return true;
}
 
int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {

    int l = 0, r = n;
    while(l < r){
        int mid = (l + r) / 2;
        bool tmp = calc(n, S, mid, X, Y);
        //cerr << mid << " " << tmp << "\n";
        if(tmp) r = mid;
        else l = mid + 1;
    }
    //cerr << "ans " << l << "\n";
    calc(n, S, l, X, Y);
 
    for(int i = 0; i < ans.size(); i++){
        P[i] = ans[i].F;
        Q[i] = ans[i].Sc;
    }
    
	return ans.size();
}

Compilation message (stderr)

sorting.cpp: In function 'bool calc(int, int*, int, int*, int*)':
sorting.cpp:50: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]
   50 |     while(ans.size() < m) ans.eb(mp(0, 0));
      |           ~~~~~~~~~~~^~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
sorting.cpp:75:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |  return ans.size();
      |         ~~~~~~~~^~
sorting.cpp:57:39: warning: unused parameter 'm' [-Wunused-parameter]
   57 | int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {
      |                                   ~~~~^

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