Submission #532835

#	Time	Username	Problem	Language	Result	Execution time	Memory
532835		ivan24	Sorting (IOI15_sorting)	C++14	100 / 100	706 ms	27948 KiB

sorting

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

using ll = long long int;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
#define F first
#define S second

ll min (ll x, ll y){
    return ((x < y) ? x : y);
}

ll max (ll x, ll y){
    return ((x > y) ? x : y);
}

const ll INF = 1e18;

int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) {
    cout.setstate(ios_base::failbit);

    p[0] = 0; q[0] = 1;
    bool perfect = true;
    for (ll i = 0; n > i; i++){
        if (s[i] != i) perfect = false;
    }
    if (perfect) return 0;

    ll lo = 1,hi = m,md;
    md = (lo+hi/2);
    while (hi >= lo){
        md = (lo+hi)/2;
        cout << "md: " << md << endl;
        vi v,v_idx;
        v.resize(n);
        v_idx.resize(n);
        for (ll i = 0; n > i; i++){
            v[i] = s[i]; v_idx[v[i]] = i;
        }
        for (ll i = 0; md > i; i++){
            swap(v[x[i]],v[y[i]]);
            swap(v_idx[v[x[i]]],v_idx[v[y[i]]]);
        }
        vi cur,cur_idx;
        cur.resize(n);
        cur_idx.resize(n);
        vii swaps;
        swaps.assign(md,ii(0,0));
        for (ll i = 0; n > i; i++){
            cur[i] = i; cur_idx[i] = i;
        }
        /*
        cout << "v: ";
        for (auto i: v) cout << i << " ";
        cout << endl;
        cout << "v_idx: ";
        for (auto i: v_idx) cout << i << " ";
        cout << endl;
        cout << "cur: ";
        for (auto i: cur) cout << i << " ";
        cout << endl;
        cout << "cur_idx: ";
        for (auto i: cur_idx) cout << i << " ";
        cout << endl;
        */
        ll ptr = 0;
        for (ll i = md-1; i >= 0; i--){
            while (n > ptr && cur_idx[ptr] == v_idx[ptr]) ptr++;
            if (ptr >= n) continue;
            //cout << ptr << endl;
            swaps[i] = ii(cur_idx[ptr],cur_idx[v[cur_idx[ptr]]]);
            swap(cur[cur_idx[ptr]],cur[cur_idx[v[cur_idx[ptr]]]]);
            swap(cur_idx[ptr],cur_idx[v[cur_idx[ptr]]]);
            /*
            cout << "swapped: " << swaps[i].F << " and " << swaps[i].S << " ptr: " << ptr << endl;
            cout << "cur: ";
            for (auto i: cur) cout << i << " ";
            cout << endl;
            cout << "cur_idx: ";
            for (auto i: cur_idx) cout << i << " ";
            cout << endl;
            cout << "v: ";
            for (auto i: v) cout << i << " ";
            cout << endl;
            cout << "v_idx: ";
            for (auto i: v_idx) cout << i << " ";
            cout << endl;
            */

            swap(v_idx[v[x[i]]], v_idx[v[y[i]]]);
            swap(v[x[i]],v[y[i]]);
            swap(cur_idx[cur[x[i]]],cur_idx[cur[y[i]]]);
            swap(cur[x[i]],cur[y[i]]);
        }
        bool works = true;
        for (ll i = 0; n > i; i++) works = works && (cur[i] == v[i]);
        /*
        cout << "after: \n";
        cout << "v: ";
        for (auto i: v) cout << i << " ";
        cout << endl;
        cout << "v_idx: ";
        for (auto i: v_idx) cout << i << " ";
        cout << endl;
        cout << "cur: ";
        for (auto i: cur) cout << i << " ";
        cout << endl;
        cout << "cur_idx: ";
        for (auto i: cur_idx) cout << i << " ";
        cout << endl;
        */
        if (works){
            hi = md;
            for (ll i = 0; md > i; i++){
                p[i] = swaps[i].F;
                q[i] = swaps[i].S;
            }
        }else
            lo = md+1;
        if (hi == lo && hi == md) return md;
    }
	return md;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:11:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   11 | #define F first
sorting.cpp:120:33: note: in expansion of macro 'F'
  120 |                 p[i] = swaps[i].F;
      |                                 ^
sorting.cpp:12:11: warning: conversion from 'long long int' to 'int' may change value [-Wconversion]
   12 | #define S second
sorting.cpp:121:33: note: in expansion of macro 'S'
  121 |                 q[i] = swaps[i].S;
      |                                 ^
sorting.cpp:125:42: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  125 |         if (hi == lo && hi == md) return md;
      |                                          ^~
sorting.cpp:127:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  127 |  return md;
      |         ^~

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