Submission #432513

#TimeUsernameProblemLanguageResultExecution timeMemory
432513snasibov05Sorting (IOI15_sorting)C++14
54 / 100
1065 ms76888 KiB
#include "sorting.h" #include <vector> #include <cassert> #include <algorithm> using namespace std; #define pii pair<int, int> #define f first #define s second #define pb push_back int findSwapPairs(int n, int s[], int m, int x[], int y[], int p[], int q[]) { vector<vector<int>> v(m+1, vector<int>(n)); vector<vector<int>> idx(m+1, vector<int>(n)); for (int i = 0; i < n; ++i) { v[0][i] = s[i]; idx[0][s[i]] = i; } if (is_sorted(v[0].begin(), v[0].end())) return 0; for (int i = 1; i <= m; ++i) { v[i] = v[i-1]; idx[i] = idx[i-1]; swap(idx[i][v[i][x[i-1]]], idx[i][v[i][y[i-1]]]); swap(v[i][x[i-1]], v[i][y[i-1]]); vector<int> final = idx[i]; vector<int> arr = v[i]; vector<pii> swaps; for (int j = 0; j < n; ++j) { if (final[j] == j) continue; int k = final[j]; swaps.pb({j, k}); final[arr[j]] = k; arr[k] = arr[j]; arr[j] = j; } if (swaps.size() > i) continue; arr = v[i]; for (int j = 0; j < m; ++j) { p[i] = q[i] = 0; } int k = swaps.size(); for (int l = 1; l <= k; ++l){ if (is_sorted(v[l].begin(), v[l].end())) return l; int a = idx[l][arr[swaps[l-1].f]]; int b = idx[l][arr[swaps[l-1].s]]; p[l-1] = a, q[l-1] = b; swap(idx[l][arr[swaps[l-1].f]], idx[l][arr[swaps[l-1].s]]); swap(v[l][a], v[l][b]); swap(arr[swaps[l-1].f], arr[swaps[l-1].s]); if (is_sorted(v[l].begin(), v[l].end())) return l; for (int j = l+1; j <= i; ++j) { v[j] = v[j-1]; idx[j] = idx[j-1]; swap(idx[j][v[j][x[j-1]]], idx[j][v[j][y[j-1]]]); swap(v[j][x[j-1]], v[j][y[j-1]]); } } return i; } assert(false); }

Compilation message (stderr)

sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:43:26: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |         if (swaps.size() > i) continue;
      |             ~~~~~~~~~~~~~^~~
sorting.cpp:51:27: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   51 |         int k = swaps.size();
      |                 ~~~~~~~~~~^~
#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...