Submission #420917

#TimeUsernameProblemLanguageResultExecution timeMemory
420917yuto1115Arranging Shoes (IOI19_shoes)C++17
30 / 100
1090 ms16668 KiB
#include "shoes.h" #include <bits/stdc++.h> #define rep(i, n) for(ll i = 0; i < ll(n); i++) #define rep2(i, s, n) for(ll i = ll(s); i < ll(n); i++) #define rrep(i, n) for(ll i = ll(n)-1; i >= 0; i--) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define pb push_back #define eb emplace_back using namespace std; using ll = long long; using P = pair<int, int>; using vi = vector<int>; using vvi = vector<vi>; using vl = vector<ll>; using vvl = vector<vl>; using vp = vector<P>; using vvp = vector<vp>; using vb = vector<bool>; using vvb = vector<vb>; using vs = vector<string>; template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } const int inf = 1001001001; const ll linf = 1001001001001001001; ll count_swaps(vi s) { int n = s.size() / 2; vvi l(n), r(n); rep(i, 2 * n) { if (s[i] < 0) l[-s[i] - 1].pb(i); else r[s[i] - 1].pb(i); } vp v; rep(i, n) rep(j, l[i].size()) v.eb(l[i][j], r[i][j]); assert(v.size() == n); vi ord(n); iota(all(ord), 0); ll ans = inf; auto calc_inv = [&](const vi &ls) { int res = 0; rep(i, 2 * n) rep2(j, i + 1, 2 * n) { res += ls[i] > ls[j]; } return res; }; do { vi now; rep(i, n) { now.pb(v[ord[i]].first); now.pb(v[ord[i]].second); } chmin<ll>(ans, calc_inv(now)); } while (next_permutation(all(ord))); return ans; }

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from shoes.cpp:2:
shoes.cpp: In function 'll count_swaps(vi)':
shoes.cpp:53:21: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     assert(v.size() == n);
      |            ~~~~~~~~~^~~~
#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...