Submission #976792

#TimeUsernameProblemLanguageResultExecution timeMemory
976792efedmrlrArranging Shoes (IOI19_shoes)C++17
50 / 100
1097 ms26672 KiB
#include <bits/stdc++.h> #include "shoes.h" #define lli long long int #define ld long double #define pb push_back #define MP make_pair #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define REP(i, n) for(int i = 0; (i) < (n); (i)++) using namespace std; void fastio() { ios_base::sync_with_stdio(false); cin.tie(NULL); } const int N = 1e5 + 5; const int INF = 1e9 + 500; long long count_swaps(std::vector<int> s) { int n = (int)s.size() / 2; map<int, vector<int> > occ; for(int i = 0; i < 2*n; i++) { occ[s[i]].pb(i); } vector<array<int, 2> > pr; for(int i = 1; i <= n; i++) { auto &x = occ[i]; auto &y = occ[-i]; for(int j = 0; j < x.size(); j++) { pr.pb({y[j], x[j]}); } } vector<int> ord(2 * n, 0); sort(all(pr), [](array<int, 2> &x, array<int, 2> &y) { return x[0] + x[1] < y[0] + y[1]; }); for(int i = 0; i < n; i++) { ord[pr[i][0]] = i * 2; ord[pr[i][1]] = i * 2 + 1; } lli inv = 0; for(int i = 0; i < 2 * n; i++) { for(int j = i + 1; j < 2 * n; j++) { if(ord[i] > ord[j]) { inv++; } } } return inv; }

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:35:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |         for(int j = 0; j < x.size(); j++) {
      |                        ~~^~~~~~~~~~
#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...