제출 #552027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
552027		Theo830	정렬하기 (IOI15_sorting)	C++17	100 / 100	333 ms	21828 KiB

sorting

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "sorting.h"
int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    int n = N;
    int m = M;
    if(is_sorted(S,S+N)){
        return 0;
    }
    ll l = 1,r = m;
    ll ans = m;
    while(l <= r){
        ll mid = (l+r)/2;
        int cur[n];
        int fin[n];
        int pos[n],post[n];
        f(i,0,n){
            pos[S[i]] = i;
        }
        f(i,0,n){
            cur[i] = S[i];
            fin[i] = S[i];
        }
        f(j,0,mid){
            swap(fin[X[j]],fin[Y[j]]);
        }
        f(i,0,n){
            post[fin[i]] = i;
        }
        ll po = 0;
        f(j,0,mid){
            swap(pos[cur[X[j]]],pos[cur[Y[j]]]);
            swap(cur[X[j]],cur[Y[j]]);
            while(po < n && fin[po] == po){
                po++;
            }
            if(po < n){
                ll xx = pos[po],yy = pos[fin[po]];
                swap(pos[cur[xx]],pos[cur[yy]]);
                swap(cur[xx],cur[yy]);
                xx = post[po],yy = post[fin[po]];
                swap(post[fin[xx]],post[fin[yy]]);
                swap(fin[xx],fin[yy]);
            }
        }
        while(po < n && fin[po] == po){
            po++;
        }
        if(po == n){
            r = mid - 1;
            ans = min(ans,mid);
        }
        else{
            l = mid + 1;
        }
    }
    int cur[n];
    int fin[n];
    int pos[n],post[n];
    f(i,0,n){
        pos[S[i]] = i;
    }
    f(i,0,n){
        cur[i] = S[i];
        fin[i] = S[i];
    }
    f(j,0,ans){
        swap(fin[X[j]],fin[Y[j]]);
    }
    f(i,0,n){
        post[fin[i]] = i;
    }
    ll po = 0;
    f(j,0,ans){
        swap(pos[cur[X[j]]],pos[cur[Y[j]]]);
        swap(cur[X[j]],cur[Y[j]]);
        while(po < n && fin[po] == po){
            po++;
        }
        if(po < n){
            ll xx = pos[po],yy = pos[fin[po]];
            P[j] = xx,Q[j] = yy;
            swap(pos[cur[xx]],pos[cur[yy]]);
            swap(cur[xx],cur[yy]);
            xx = post[po],yy = post[fin[po]];
            swap(post[fin[xx]],post[fin[yy]]);
            swap(fin[xx],fin[yy]);
        }
        else{
            P[j] = Q[j] = 0;
        }
    }
	return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:40:25: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   40 |             pos[S[i]] = i;
      |                         ^
sorting.cpp:50:28: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   50 |             post[fin[i]] = i;
      |                            ^
sorting.cpp:83:21: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   83 |         pos[S[i]] = i;
      |                     ^
sorting.cpp:93:24: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
   93 |         post[fin[i]] = i;
      |                        ^
sorting.cpp:104:20: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |             P[j] = xx,Q[j] = yy;
      |                    ^~
sorting.cpp:104:30: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  104 |             P[j] = xx,Q[j] = yy;
      |                              ^~
sorting.cpp:115:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  115 |  return ans;
      |         ^~~

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