Submission #1245091

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245091		caacrugon	Sorting (IOI15_sorting)	C++20	Compilation error	0 ms	0 KiB

sorting

#include "sorting.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define first f
#define second s

ll n;
vector<ll> ln;
vector<pair<ll,ll>> em;

bool possi(ll m){
    vector<ll> a=ln;
    ll limit=m;
    for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
    int N=n;
    vector<pair<ll,int>> temp;
    for(int i=0;i<N;i++) temp.push_back({a[i],i});
    sort(temp.begin(),temp.end());
    vector<int> p(N);
    for(int i=0;i<N;i++) p[temp[i].second]=i;
    vector<bool> vis(N,false);
    ll cycles=0;
    for(int i=0;i<N;i++) if(!vis[i]){
        int j=i;
        while(!vis[j]){
            vis[j]=true;
            j=p[j];
        }
        cycles++;
    }
    ll min_swaps=N-cycles;
    return min_swaps<=m;
}

int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) {
    ln.resize(N);
    n=N;
    em.resize(M);
    for(int i=0;i<N;i++){
        ln[i]=S[i];
    }
    for(int i=0;i<M;i++){
        em[i].first=X[i];
        em[i].second=Y[i];
    }
    ll l=0,r=M,ans=M;
    while(l<=r){
        ll m=l+((r-l)/2);
        if(possi(m)){
            ans=m;
            r=m-1;
        }else{
            l=m+1;
        }
    }
    vector<ll> a=ln;
    ll limit=ans;
    for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
    vector<pair<ll,int>> temp;
    for(int i=0;i<N;i++) temp.push_back({a[i],i});
    sort(temp.begin(),temp.end());
    vector<int> p(N);
    for(int i=0;i<N;i++) p[temp[i].second]=i;
    vector<bool> vis(N,false);
    for(int i=0;i<N;i++){ 
      if(!vis[i] && p[i]!=i){
        int cur=i;
        vector<int> ciclo;
        while(!vis[cur]){
            ciclo.push_back(cur);
            vis[cur]=true;
            cur=p[cur];
        }
        for(int j=1;j<ciclo.size();j++){
            P[R]=ciclo[0];
            Q[R]=ciclo[j];
        }
      }
    }
    return ans;
}

Compilation message (stderr)

sorting.cpp: In function 'bool possi(long long int)':
sorting.cpp:7:15: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 'f'
    7 | #define first f
      |               ^
sorting.cpp:17:42: note: in expansion of macro 'first'
   17 |     for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
      |                                          ^~~~~
sorting.cpp:8:16: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 's'
    8 | #define second s
      |                ^
sorting.cpp:17:57: note: in expansion of macro 'second'
   17 |     for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
      |                                                         ^~~~~~
sorting.cpp:8:16: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'struct std::pair<long long int, int>'} has no member named 's'
    8 | #define second s
      |                ^
sorting.cpp:23:36: note: in expansion of macro 'second'
   23 |     for(int i=0;i<N;i++) p[temp[i].second]=i;
      |                                    ^~~~~~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:7:15: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 'f'
    7 | #define first f
      |               ^
sorting.cpp:46:15: note: in expansion of macro 'first'
   46 |         em[i].first=X[i];
      |               ^~~~~
sorting.cpp:8:16: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 's'
    8 | #define second s
      |                ^
sorting.cpp:47:15: note: in expansion of macro 'second'
   47 |         em[i].second=Y[i];
      |               ^~~~~~
sorting.cpp:7:15: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 'f'
    7 | #define first f
      |               ^
sorting.cpp:61:42: note: in expansion of macro 'first'
   61 |     for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
      |                                          ^~~~~
sorting.cpp:8:16: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, long long int> >, std::pair<long long int, long long int> >::value_type' {aka 'struct std::pair<long long int, long long int>'} has no member named 's'
    8 | #define second s
      |                ^
sorting.cpp:61:57: note: in expansion of macro 'second'
   61 |     for(ll i=0;i<limit;i++) swap(a[em[i].first],a[em[i].second]);
      |                                                         ^~~~~~
sorting.cpp:8:16: error: '__gnu_cxx::__alloc_traits<std::allocator<std::pair<long long int, int> >, std::pair<long long int, int> >::value_type' {aka 'struct std::pair<long long int, int>'} has no member named 's'
    8 | #define second s
      |                ^
sorting.cpp:66:36: note: in expansion of macro 'second'
   66 |     for(int i=0;i<N;i++) p[temp[i].second]=i;
      |                                    ^~~~~~
sorting.cpp:78:15: error: 'R' was not declared in this scope
   78 |             P[R]=ciclo[0];
      |               ^