oj.uz

Submission #727748

# Submission time Handle Problem Language Result Execution time Memory
727748 2023-04-21T09:17:42 Z Vu_CG_Coder Sorting (IOI15_sorting) C++14
16 / 100
 1 ms 596 KB 
/* [Author : Hoang Duy Vu] - THPT Chuyen Nguyen Du    */
//#pragma GCC optimize(" unroll-loops")
//#pragma gcc optimize("Ofast")
//#pragma GCC optimization("Ofast")
//#pragma optimize(Ofast)
#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;

    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]);
    }

    if (X[0] == 0 && Y[0] == 1){

    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);

    }
    else calc(0,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;
}

// int main()
// {
//     ios_base::sync_with_stdio(0);
//     cin.tie(NULL); cout.tie(NULL);
//     if(fopen(TASK".inp", "r")){
//     freopen(TASK".inp","r",stdin);
//     freopen(TASK".out","w",stdout);
//     }

//     int x[Nx] , y[Nx] , s[Nx] , t[Nx] , q[Nx];

//     int r , o;
//     cin >> r >> o;
//     for (int i = 0 ; i < r ; i++) cin >> s[i];
//     for (int i = 0 ; i < o ; i++) 
//         cin >> x[i] >> y[i];

//     findSwapPairs(r,s,o,x,y,t,q);
//     return 0;
// }

Compilation message

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:102: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]
  102 |     while (p.size() < m) p.push_back(C(0,0));
      |            ~~~~~~~~~^~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Incorrect 0 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -