Submission #474213

#TimeUsernameProblemLanguageResultExecution timeMemory
474213jwvg0425Sorting (IOI15_sorting)C++17
100 / 100
676 ms33916 KiB
#include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <iostream> #include <string> #include <bitset> #include <map> #include <set> #include <tuple> #include <string.h> #include <math.h> #include <random> #include <functional> #include <assert.h> #include <math.h> #include "sorting.h" #define all(x) (x).begin(), (x).end() #define xx first #define yy second using namespace std; template<typename T, typename Pr = less<T>> using pq = priority_queue<T, vector<T>, Pr>; using i64 = long long int; using ii = pair<int, int>; using ii64 = pair<i64, i64>; bool sorted(vector<int> s) { for (int i = 0; i < s.size(); i++) if (s[i] != i) return false; return true; } vector<ii> solve(vector<int> s, vector<ii> r, int k) { int n = s.size(); r.resize(k); int m = r.size(); vector<ii> res; vector<int> rev(n), idx(n), pos(n); for (int j = 0; j < n; j++) pos[s[j]] = j; for (int j = 0; j < n; j++) rev[j] = j; for (int j = 0; j < m; j++) swap(rev[r[j].xx], rev[r[j].yy]); for (int j = 0; j < n; j++) idx[rev[j]] = j; int nxt = 0; for (int i = 0; i < m; i++) { swap(s[r[i].xx], s[r[i].yy]); swap(pos[s[r[i].xx]], pos[s[r[i].yy]]); int a = idx[r[i].xx], b = idx[r[i].yy]; swap(rev[a], rev[b]); swap(idx[rev[a]], idx[rev[b]]); // s[x] -> idx[x] bool f = false; while (nxt < n && !f) { int x = pos[nxt]; if (s[x] == idx[x]) { nxt++; continue; } int y = rev[nxt]; res.emplace_back(x, y); swap(s[x], s[y]); swap(pos[s[x]], pos[s[y]]); f = true; nxt++; } if (!f) res.emplace_back(0, 0); } if (!sorted(s)) { res.clear(); res.emplace_back(-1, -1); } return res; } int findSwapPairs(int N, int S[], int M, int X[], int Y[], int P[], int Q[]) { vector<int> s(N); vector<ii> r(M); for (int i = 0; i < N; i++) s[i] = S[i]; for (int i = 0; i < M; i++) { r[i].xx = X[i]; r[i].yy = Y[i]; } int lo = 0, hi = M; vector<ii> res; while (lo <= hi) { int mid = (lo + hi) / 2; auto now = solve(s, r, mid); if (!now.empty() && now[0].xx == -1) { lo = mid + 1; } else { res = now; hi = mid - 1; } } for (int i = 0; i < res.size(); i++) { P[i] = res[i].xx; Q[i] = res[i].yy; } return res.size(); }

Compilation message (stderr)

sorting.cpp: In function 'bool sorted(std::vector<int>)':
sorting.cpp:32:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |  for (int i = 0; i < s.size(); i++)
      |                  ~~^~~~~~~~~~
sorting.cpp: In function 'std::vector<std::pair<int, int> > solve(std::vector<int>, std::vector<std::pair<int, int> >, int)':
sorting.cpp:41:16: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   41 |  int n = s.size();
      |          ~~~~~~^~
sorting.cpp:43:16: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   43 |  int m = r.size();
      |          ~~~~~~^~
sorting.cpp: In function 'int findSwapPairs(int, int*, int, int*, int*, int*, int*)':
sorting.cpp:134:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |  for (int i = 0; i < res.size(); i++)
      |                  ~~^~~~~~~~~~~~
sorting.cpp:140:17: warning: conversion from 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  140 |  return res.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...