제출 #552027

#제출 시각아이디문제언어결과실행 시간메모리
552027Theo830정렬하기 (IOI15_sorting)C++17
100 / 100
333 ms21828 KiB
#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;
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...