Submission #452147

#TimeUsernameProblemLanguageResultExecution timeMemory
452147PedroBigManSorting (IOI15_sorting)C++14
100 / 100
432 ms24548 KiB
#include "sorting.h" /* Author of all code: Pedro BIGMAN Dias Last edit: 15/02/2021 */ #pragma GCC optimization ("O3") #pragma GCC optimization ("unroll-loops") #pragma GCC optimize("Ofast") #include <iostream> #include <vector> #include <cmath> #include <algorithm> #include <string> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <deque> #include <list> #include <iomanip> #include <stdlib.h> #include <time.h> #include <cstring> using namespace std; typedef long long int ll; typedef unsigned long long int ull; typedef long double ld; #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++) #define pb push_back #define mp make_pair #define pl pair<ll,ll> #define ff first #define ss second #define whole(x) x.begin(),x.end() #define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl #define INF 500000000LL #define EPS 0.00000001 #define pi 3.14159 ll mod=1000000007LL; template<class A=ll> void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;} template<class A=ll> void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} vector<vector<ll> > CycleDecomp(vector<ll> p) //cycle decomposition of permutation { ll N = p.size(); vector<vector<ll> > ans; vector<ll> cur; vector<bool> visited; REP(i,0,N) {visited.pb(false);} ll node; REP(i,0,N) { if(visited[i]) {continue;} node=i; cur.pb(node); node=p[node]; while(node!=i) { cur.pb(node); node=p[node]; } REP(i,0,cur.size()) {visited[cur[i]]=true;} ans.pb(cur); cur.clear(); } return ans; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { vector<ll> p; REP(i,0,N) {p.pb(i);} ll lo=0; ll hi=M; ll mid; ll R; while(lo<hi) { mid=(hi+lo)/2; REP(i,0,N) {p[i]=S[i];} REP(i,0,mid) {swap(p[X[i]],p[Y[i]]);} ll trans = N-CycleDecomp(p).size(); if(trans<=mid) {hi=mid;} else {lo=mid+1;} } R=lo; REP(i,0,N) {p[i]=S[i];} REP(i,0,R) {swap(p[X[i]],p[Y[i]]);} vector<vector<ll> > cycles = CycleDecomp(p); vector<pl> swa; REP(i,0,cycles.size()) { REP(j,0,cycles[i].size()-1) {swa.pb({cycles[i][j],cycles[i][j+1]});} } //REP(i,0,swa.size()) {cout<<swa[i].ff<<" "<<swa[i].ss<<endl;} REP(i,0,N) {p[i]=S[i];} vector<ll> pos; REP(i,0,N) {pos.pb(0LL);} REP(i,0,N) {pos[p[i]]=i;} REP(i,0,swa.size()) { pos[p[X[i]]]=Y[i]; pos[p[Y[i]]]=X[i]; swap(p[X[i]],p[Y[i]]); P[i]=pos[swa[i].ff]; Q[i]=pos[swa[i].ss]; swap(pos[swa[i].ff],pos[swa[i].ss]); swap(p[P[i]],p[Q[i]]); } REP(i,swa.size(),R) {P[i]=0LL; Q[i]=0LL;} //cout<<R<<endl; REP(i,0,R) {cout<<P[i]<<" "<<Q[i]<<endl;} return R; }

Compilation message (stderr)

sorting.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("O3")
      | 
sorting.cpp:7: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    7 | #pragma GCC optimization ("unroll-loops")
      | 
sorting.cpp: In function 'std::vector<std::vector<long long int> > CycleDecomp(std::vector<long long int>)':
sorting.cpp:61:7: warning: declaration of 'i' shadows a previous local [-Wshadow]
   61 |   REP(i,0,cur.size()) {visited[cur[i]]=true;}
      |       ^
sorting.cpp:29:27: note: in definition of macro 'REP'
   29 | #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
      |                           ^
sorting.cpp:53:6: note: shadowed declaration is here
   53 |  REP(i,0,N)
      |      ^
sorting.cpp:29:27: note: in definition of macro 'REP'
   29 | #define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
      |                           ^
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:97:21: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |   P[i]=pos[swa[i].ff]; Q[i]=pos[swa[i].ss];
      |                     ^
sorting.cpp:97:42: warning: conversion from '__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   97 |   P[i]=pos[swa[i].ff]; Q[i]=pos[swa[i].ss];
      |                                          ^
sorting.cpp:102:9: warning: conversion from 'll' {aka 'long long int'} to 'int' may change value [-Wconversion]
  102 |  return R;
      |         ^
#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...