Submission #432988

#	Time	Username	Problem	Language	Result	Execution time	Memory
432988		wiwiho	Sorting (IOI15_sorting)	C++14	74 / 100	1072 ms	15728 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 mn = m + 1, mnp = -1;
    for(int i = 0; i < mn; i++){
        bool tmp = calc(n, S, i, X, Y);
        if(tmp){
            if(ans.size() < mn){
                mn = ans.size();
                mnp = i;
            }
        }
        else assert(mnp == -1);
    }
    calc(n, S, mnp, 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:63:27: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   63 |             if(ans.size() < mn){
      |                ~~~~~~~~~~~^~~~
sorting.cpp:64:30: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   64 |                 mn = ans.size();
      |                      ~~~~~~~~^~
sorting.cpp:72: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]
   72 |     for(int i = 0; i < ans.size(); i++){
      |                    ~~^~~~~~~~~~~~
sorting.cpp:77:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   77 |  return ans.size();
      |         ~~~~~~~~^~

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