oj.uz

답안 #727765

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
727765 2023-04-21T09:39:45 Z Vu_CG_Coder 정렬하기 (IOI15_sorting) C++14
20 / 100
 2 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]);
    }

    // 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 (ii v : p) cout << v.fi << " " << v.se << "\n";

   //  for (int i = 0 ; i < n ; i++) cout << S[i] << " ";
   //  cout << "\n";

    for (int i = 0 ; i < p.size() ; i++) P[i] = p[i].fi,Q[i] = p[i].se;

  //  for (int i = 0 ; i < p.size() ; i++) cout << P[i] << " " << Q[i] << "\n";
    return p.size();
}

// 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:126:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |     for (int i = 0 ; i < p.size() ; i++) P[i] = p[i].fi,Q[i] = p[i].se;
      |                      ~~^~~~~~~~~~
sorting.cpp:129:18: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  129 |     return p.size();
      |            ~~~~~~^~

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 316 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 308 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 316 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Incorrect 1 ms 212 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -