Submission #432970

#	Time	Username	Problem	Language	Result	Execution time	Memory
432970		wiwiho	Sorting (IOI15_sorting)	C++14	0 / 100	7 ms	460 KiB

sorting

#include "sorting.h"

#include <bits/stdc++.h>

#define printv(a, b) { \
    for(auto pv : a) b << pv << " "; \
    b << "\n"; \
}
#define mp make_pair
#define F first
#define Sc second
#define eb emplace_back

using namespace std;

typedef long long ll;

using pii = pair<int, int>;

const ll MOD = 1000000007;

int findSwapPairs(int n, int S[], int m, int X[], int Y[], int P[], int Q[]) {

    vector<int> s(n);
    for(int i = 0; i < n; i++) s[i] = S[i];

    vector<int> num(n);
    vector<int> pos(n);
    for(int i = 0; i < n; i++) num[i] = pos[i] = i;
    for(int i = 0; i < m; i++){
        swap(num[pos[X[i]]], num[pos[Y[i]]]);
        swap(pos[X[i]], pos[Y[i]]);
        /*cerr << "num ";
        printv(num, cerr);
        cerr << "pos ";
        printv(pos, cerr);*/
    }
    /*cerr << "num ";
    printv(num, cerr);
    cerr << "pos ";
    printv(pos, cerr);*/
    

    vector<pii> ans;
    int cnt = 0;
    vector<int> now(n), np(n);
    for(int i = 0; i < n; i++) now[i] = i, np[i] = i;
    for(int i = 0; i < n; i++){
        while(s[i] != num[i]){
            //cerr << "test " << cnt << "\n";
            swap(now[np[X[cnt]]], now[np[Y[cnt]]]);
            swap(np[X[cnt]], np[Y[cnt]]);
            //printv(now, cerr);
            cnt++;
            ans.eb(mp(now[i], now[pos[s[i]]]));
            swap(s[i], s[pos[s[i]]]);
            //printv(s, cerr);
        }
    }

    while(ans.size() < m) ans.eb(mp(0, 0));
    for(int i = 0; i < m; i++){
        P[i] = ans[i].F;
        Q[i] = ans[i].Sc;
    }

    for(int i = 0; i < m; i++){
        //cerr << "round " << i << "\n";
        swap(S[X[i]], S[Y[i]]);
        //for(int j = 0; j < n; j++) cerr << S[j] << " ";
        //cerr << "\n";
        swap(S[P[i]], S[Q[i]]);
        //for(int j = 0; j < n; j++) cerr << S[j] << " ";
        //cerr << "\n";
        bool ok = true;
        for(int i = 0; i < n; i++) if(S[i] != i) ok = false;
        if(ok) return i + 1;
    }
    //for(int i = 0; i < n; i++) assert(S[i] == i);
    
	return m;
}

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:61:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   61 |     while(ans.size() < m) ans.eb(mp(0, 0));
      |           ~~~~~~~~~~~^~~
sorting.cpp:76:17: warning: declaration of 'i' shadows a previous local [-Wshadow]
   76 |         for(int i = 0; i < n; i++) if(S[i] != i) ok = false;
      |                 ^
sorting.cpp:67:13: note: shadowed declaration is here
   67 |     for(int i = 0; i < m; i++){
      |             ^

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