Submission #834291

#	Time	Username	Problem	Language	Result	Execution time	Memory
834291		Victor	Sorting (IOI15_sorting)	C++17	100 / 100	204 ms	18436 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define trav(a, x) for (auto &a : x)

#define all(x) x.begin(), x.end()
#define sz(x) x.size()
#define pb push_back

typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;

const ll INF = 1'000'000'007;

bool isSorted(int N, int S[]) {
    rep(i,0,N) if(S[i]!=i) return false;
    return true;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    P[0] = 0;
    Q[0] = 0;

    vll s;
    ll n=N;
    ll lo=0,hi=M;
    while(lo!=hi) {
        //cout<<"lo = "<<lo<<" hi = "<<hi<<endl;
        ll mid=(lo+hi)/2;
        rep(i,0,n) s.pb(S[i]);
        rep(i,0,mid) swap(s[X[i]],s[Y[i]]);

        vpll item_swaps;
        rep(i,0,n) while(s[i]!=i) {
            //cout<<"i = "<<i<<" s[i] = "<<s[i]<<" s[s[i]] = "<<s[s[i]]<<endl;
            item_swaps.emplace_back(s[i],s[s[i]]);
            swap(s[i],s[s[i]]);
        }
        //cout<<sz(item_swaps)<<endl;
        if(sz(item_swaps)<=mid) hi=mid;
        else lo=mid+1;
        s.clear();
    }

    //cout<<"lo = "<<lo<<endl;
    rep(i,0,n) s.pb(S[i]);
    rep(i,0,lo) swap(s[X[i]],s[Y[i]]);
    //cout<<"seq"<<endl;
    //rep(i,0,n) cout<<s[i]<<' ';
    //cout<<endl;
    vpll item_swaps;
    rep(i,0,n) while(s[i]!=i) {
        item_swaps.emplace_back(s[i],s[s[i]]);
        swap(s[i],s[s[i]]);
    }


    rep(i,sz(item_swaps),lo) item_swaps.emplace_back(0,0);
    //cout<<"swaps"<<endl;
    //rep(i,0,sz(item_swaps)) cout<<item_swaps[i].first<<' '<<item_swaps[i].second<<endl;
    //cout<<endl;

    vll indexes(n);
    rep(i,0,n) indexes[S[i]]=i;
    rep(i,0,sz(item_swaps)) {
        ll a=S[X[i]],b=S[Y[i]];
        swap(S[X[i]],S[Y[i]]);
        swap(indexes[a],indexes[b]);

        tie(a,b)=item_swaps[i];
        P[i]=indexes[a];
        Q[i]=indexes[b];
        swap(S[indexes[a]],S[indexes[b]]);
        swap(indexes[a],indexes[b]);
    }

    return lo;
}

/*
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "sorting.h"

static char _buffer[1024];
static int _currentChar = 0;
static int _charsNumber = 0;
static FILE *_inputFile, *_outputFile;

static inline int _read() {
    if (_charsNumber < 0) {
        exit(1);
    }
    if (!_charsNumber || _currentChar == _charsNumber) {
        _charsNumber = (int)fread(_buffer, sizeof(_buffer[0]), sizeof(_buffer), _inputFile);
        _currentChar = 0;
    }
    if (_charsNumber <= 0) {
        return -1;
    }
    return _buffer[_currentChar++];
}

static inline int _readInt() {
    int c, x, s;
    c = _read();
    while (c <= 32) c = _read();
    x = 0;
    s = 1;
    if (c == '-') {
        s = -1;
        c = _read();
    }
    while (c > 32) {
        x *= 10;
        x += c - '0';
        c = _read();
    }
    if (s < 0) x = -x;
    return x;
}


int main()
{
	_inputFile = fopen("sorting.in", "rb");
	int N, M;
	N = _readInt();
	int *S = (int*)malloc(sizeof(int) * (unsigned int)N);
	for (int i = 0; i < N; ++i)
		S[i] = _readInt();
	M = _readInt();
	int *X = (int*)malloc(sizeof(int) * (unsigned int)M), *Y = (int*)malloc(sizeof(int) * (unsigned int)M);
	for (int i = 0; i < M; ++i) {
	    X[i] = _readInt();
	    Y[i] = _readInt();
	}
	int *P = (int*)malloc(sizeof(int) * (unsigned int)M), *Q = (int*)malloc(sizeof(int) * (unsigned int)M);
	int ans = findSwapPairs(N, S, M, X, Y, P, Q);
	printf("%d\n", ans);
	for (int i = 0; i < ans; ++i)
		printf("%d %d\n", P[i], Q[i]);
    _Exit(0);
	return 0;
}
*/

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:49:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   49 |         if(sz(item_swaps)<=mid) hi=mid;
      |                          ^
sorting.cpp:11:21: warning: conversion from 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   11 | #define sz(x) x.size()
      |                     ^
sorting.cpp:6:36: note: in definition of macro 'rep'
    6 | #define rep(i, a, b) for (int i = (a); i < (b); i++)
      |                                    ^
sorting.cpp:67:11: note: in expansion of macro 'sz'
   67 |     rep(i,sz(item_swaps),lo) item_swaps.emplace_back(0,0);
      |           ^~
sorting.cpp:6:42: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define rep(i, a, b) for (int i = (a); i < (b); i++)
      |                                          ^
sorting.cpp:74:5: note: in expansion of macro 'rep'
   74 |     rep(i,0,sz(item_swaps)) {
      |     ^~~
sorting.cpp:80:23: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   80 |         P[i]=indexes[a];
      |                       ^
sorting.cpp:81:23: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   81 |         Q[i]=indexes[b];
      |                       ^
sorting.cpp:86:12: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   86 |     return lo;
      |            ^~

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