Submission #278203

#	Time	Username	Problem	Language	Result	Execution time	Memory
278203		davitmarg	Sorting (IOI15_sorting)	C++17	0 / 100	3 ms	640 KiB

sorting

/*
DavitMarg
In a honky-tonk,
Down in Mexico
*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
#define fastIO ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int N = 3*200005;

#ifndef death
#include "sorting.h"
#endif

int x[N], y[N], s[N],a[N], pos[N],f[N],g[N];
int n, m;
vector<pair<int, int>> ans;

void add(int x, int y, bool sw = 1)
{
    if(sw)
        ans.push_back(MP(x, y));
    else
    {
        swap(g[x], g[y]);
        f[g[x]] = x;
        f[g[y]] = y;
    }
    swap(a[x], a[y]);
    pos[a[x]] = x;
    pos[a[y]] = y;
}

bool check(int k)
{
    ans.clear();
    for (int i = 0; i < n; i++)
    {
        a[i] = s[i];
        f[i] = i;
        pos[s[i]] = i;
    }
    for (int i = 0; i < k; i++)
        swap(f[x[i]], f[y[i]]);
    for (int i = 0; i < n; i++)
        g[f[i]] = i;
    int last = 0;
    for (int i = 0; i < k; i++)
    {
        add(x[i], y[i],0);
        while (last < n && pos[last] == f[last])
            last++;
        if (last >= n)
        {
            ans.push_back(MP(0, 0));
            continue;
        }
        add(pos[last], f[last]);
        last++;
    }
    return (last >= n);
}

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 l=0, r=m, mid, res=m;
    while (l <= r)
    {
        mid = (l + r) / 2;
        if (check(mid))
        {
            r = mid - 1;
            res = mid;
        }
        else
            l = mid + 1;
    }

    check(res);

    for (int i = 0; i < ans.size(); i++)
    {
        P[i] = ans[i].first;
        Q[i] = ans[i].second;
    }
    return ans.size();
}


#ifdef death
int nn, mm,ss[N], xx[N], yy[N], pp[N], qq[N];
int main()
{
    fastIO;
    cin >> nn >> mm;
    for (int i = 0; i < nn; i++)
        cin >> ss[i];
    for (int i = 0; i < mm; i++)
        cin >> xx[i] >> yy[i];
    mm=findSwapPairs(nn, ss, mm, xx, yy, pp, qq);
    for (int i = 0; i < mm; i++)
    {
        cout << pp[i] << " : " << qq[i] << endl;
        swap(ss[xx[i]], ss[yy[i]]);
        swap(ss[pp[i]], ss[qq[i]]);
    }

    cout << endl;
    for (int i = 0; i < nn; i++)
        cout << ss[i] << " ";
    cout << endl;
        
    return 0;
}
#endif

/*

5 5 
4 3 2 1 0
1 1
4 0
2 3
1 4
0 4


10 7
0 1 2 3 4 5 6 7 9 8
0 0
0 0
0 0
0 0
0 0
0 0
0 0


*/

Compilation message (stderr)

sorting.cpp: In function 'void add(int, int, bool)':
sorting.cpp:41:35: warning: declaration of 'y' shadows a global declaration [-Wshadow]
   41 | void add(int x, int y, bool sw = 1)
      |                                   ^
sorting.cpp:37:11: note: shadowed declaration is here
   37 | int x[N], y[N], s[N],a[N], pos[N],f[N],g[N];
      |           ^
sorting.cpp:41:35: warning: declaration of 'x' shadows a global declaration [-Wshadow]
   41 | void add(int x, int y, bool sw = 1)
      |                                   ^
sorting.cpp:37:5: note: shadowed declaration is here
   37 | int x[N], y[N], s[N],a[N], pos[N],f[N],g[N];
      |     ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:86:76: warning: declaration of 'N' shadows a global declaration [-Wshadow]
   86 | int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[])
      |                                                                            ^
sorting.cpp:31:11: note: shadowed declaration is here
   31 | const int N = 3*200005;
      |           ^
sorting.cpp:114:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |     for (int i = 0; i < ans.size(); i++)
      |                     ~~^~~~~~~~~~~~
sorting.cpp:119:20: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  119 |     return ans.size();
      |            ~~~~~~~~^~

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