Submission #727767

#	Time	Username	Problem	Language	Result	Execution time	Memory
727767		Vu_CG_Coder	Sorting (IOI15_sorting)	C++14	36 / 100	3 ms	968 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>
#define All(x) (x).begin(),(x).end()
#define ll long long
#define C make_pair
#define fi first
#define se second
#define two second.first
#define thr second.second
#define TASK "txt"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) {
    if (res < val) { res = val; return true; } return false; }
template<typename T> bool minimize(T &res, const T &val) {
    if (res > val) { res = val; return true; } return false; }
 
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
const int LOG = 20;
const int INF = 1e9 + 7;
const ll LNF = 1e18 + 7;
const int mod = 1e9 + 7;
const int Nx = 2e5 + 100;
 
 
ii b[Nx];
int a[Nx];
int n , m;
int cnt = 0;
vector <ii> p;
 
 
void calc(int l , int r)
{
    if (l > r) return ;
    if (l == r) return ;
 
    int mid = (l + r) >> 1;
 
  //  cout << l << " " << r << " " << mid << "\n";
 
    int j = mid + 1;
    for (int i = l ; i <= mid ; i++)
    if (a[i] > mid)
    {
        for (; j <= n ; j++) if (a[j] <= mid) break;
        p.push_back(C(i,j));
 
      //  cout << i << " " << j << " " << mid << " " << a[i] << " " << a[j] << "\n";
        swap(a[i],a[j]);
    }
 
    calc(l,mid);
    calc(mid+1,r);
}
 
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
 
    n = N;
    m = M;
    if (n == 1) return 0;
  
     if (X[0] == 0 && Y[0] == 0)
    {
        for (int i = 0 ; i < n ; i++) a[i] = S[i];
        for (int i = 0 ; i < m ; i++) b[i] = C(X[i],Y[i]);
        calc(0,n - 1);
        for (int i = 0 ; i < p.size() ; i++) P[i] = p[i].fi,Q[i] = p[i].se;
        return p.size();
    }
 
    for (int i = 0 ; i < n ; i++) a[i] = S[i];
    for (int i = 0 ; i < m ; i++) 
    {
        b[i] = C(X[i],Y[i]);
      //  swap(a[b[i].fi],a[b[i].se]);
    }
 
    swap(a[0],a[1]);
    for (int i = 0 ; i < n ; i++) if (a[i] == 0) 
    {
        swap(a[i],a[0]);
        p.push_back(C(0,i));
    }
 
    swap(a[0],a[1]);
 
    for (int i = 0 ; i < n ; i++) if (a[i] == 1)
    {
        int x = 0;
        if (a[x] == 0) x = 1;
        swap(a[i],a[x]);
        p.push_back(C(x,i));
    }
 
    // for (int i = 0 ; i < n ; i++) cout << a[i] << " ";
    // cout << "\n";
 
    calc(2,n - 1);
 
    while (p.size() < m) p.push_back(C(0,0));
 
    for (int i = 0 ; i < m ; i++)
    {
        swap(S[b[i].fi],S[b[i].se]);
        swap(S[p[i].fi],S[p[i].se]);
 
       // cout << b[i].fi << " " << b[i].se << "\n";
 
        // for (int j = 0 ; j < n ; j++) cout << S[j] << " ";
        //  cout << "\n";
    }
 
    if (S[0] == 1)
    {
        p[m - 1] = (C(0,1));
        swap(S[0],S[1]);
    }
 
    for (int i = 0 ; i < m ; i++) P[i] = p[i].fi,Q[i] = p[i].se;
    return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:68:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |         for (int i = 0 ; i < p.size() ; i++) P[i] = p[i].fi,Q[i] = p[i].se;
      |                          ~~^~~~~~~~~~
sorting.cpp:69:22: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   69 |         return p.size();
      |                ~~~~~~^~
sorting.cpp:101:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  101 |     while (p.size() < m) p.push_back(C(0,0));
      |            ~~~~~~~~~^~~

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