제출 #396048

#제출 시각아이디문제언어결과실행 시간메모리
396048usachevd0고대 책들 (IOI17_books)C++17
12 / 100
9 ms5836 KiB
#include <bits/stdc++.h> #ifndef DEBUG #include "books.h" #endif using namespace std; #define fi first #define se second #define mp make_pair #define pb push_back #define all(a) (a).begin(), (a).end() using ll = long long; using ull = unsigned long long; using pii = pair<int, int>; using pil = pair<int, ll>; using pli = pair<ll, int>; using pll = pair<ll, ll>; using ld = long double; template<typename T1, typename T2> bool chkmin(T1 &x, T2 y) { return y < x ? (x = y, true) : false; } template<typename T1, typename T2> bool chkmax(T1 &x, T2 y) { return y > x ? (x = y, true) : false; } void debug_out() { cerr << endl; } template<typename T1, typename... T2> void debug_out(T1 A, T2... B) { cerr << ' ' << A; debug_out(B...); } template<typename T> void mdebug_out(T* a, int n) { for (int i = 0; i < n; ++i) { cerr << a[i] << ' '; } cerr << endl; } #ifdef DEBUG #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define mdebug(a, n) cerr << #a << ": ", mdebug_out(a, n) #else #define debug(...) 1337 #define mdebug(a, n) 1337 #endif template<typename T> ostream& operator << (ostream& stream, const vector<T> &v) { for (auto& x : v) { stream << x << ' '; } return stream; } template<typename T1, typename T2> ostream& operator << (ostream& stream, const pair<T1, T2>& p) { return stream << p.first << ' ' << p.second; } const int maxN = 1000006; const int INF32 = 1e9; int n; namespace fnw { int f[maxN]; void add(int i) { for (++i; i < maxN; i += i & -i) { ++f[i]; } } int pref(int i) { int ans = 0; for (++i; i >= 1; i -= i & -i) { ans += f[i]; } return ans; } } namespace dsu { int q[maxN]; void reset() { memset(q, 255, sizeof q); } int gt(int x) { return q[x] < 0 ? x : q[x] = gt(q[x]); } bool un(int x, int y) { x = gt(x); y = gt(y); if (x == y) return false; if (-q[x] < -q[y]) swap(x, y); q[x] += q[y]; q[y] = x; return true; } } ll minimum_walk(vector<int> p, int s) { n = p.size(); ll ans = 0; int mn = 1e9; int mx = -1e9; dsu::reset(); for (int i = 0; i + 1 < n; ++i) { fnw::add(p[i]); int r = i + 1 - fnw::pref(i); if (r > 0) { ans += 2 * r; dsu::un(i, i + 1); chkmin(mn, i); chkmax(mx, i + 1); } } /*if (s == 0) { chkmin(mn, 0); for (int i = mn; i < mx; ++i) { if (dsu::un(i, i + 1)) { ans += 2; } } return ans; }*/ vector<int> comp(n, -1); vector<int> min_comp(n, +INF32); vector<int> max_comp(n, -INF32); int C = 0; for (int x = 0; x < n; ++x) if (comp[x] == -1 && (p[x] != x || x == s)) { int y = x; min_comp[C] = x; do { comp[y] = C; chkmax(max_comp[C], y); y = p[y]; } while (y != x); ++C; } debug(comp); vector<pii> G[C]; for (int c = 0; c < C; ++c) { int l = min_comp[c]; int r = max_comp[c]; for (int i = 0; i < n; ++i) if (comp[i] != c && (p[i] != i || i == s)) { int dist; if (i < l) dist = l - i; else if (i > r) dist = i - r; else dist = 0; debug(c, comp[i], dist); G[c].emplace_back(comp[i], dist); } } vector<int> dist(C, INF32); vector<int> par_w(C, 0); dist[comp[s]] = 0; multiset<pii> pq; pq.insert({0, comp[s]}); while (!pq.empty()) { int v = pq.begin()->se; int _d = pq.begin()->fi; pq.erase(pq.begin()); if (_d != dist[v]) continue; for (auto& e : G[v]) { int u = e.fi; int w = e.se; if (chkmin(dist[u], w)) { par_w[u] = w; pq.insert(mp(dist[u], u)); } } } debug(dist); debug(par_w); for (int c = 0; c < C; ++c) { ans += 2 * par_w[c]; } return ans; } #ifdef DEBUG int32_t main() { #ifdef DEBUG freopen("in", "r", stdin); #endif ios::sync_with_stdio(0); cin.tie(0); int n, s; cin >> n >> s; vector<int> p(n); for (auto& x : p) cin >> x; cout << minimum_walk(p, s) << '\n'; return 0; } #endif

컴파일 시 표준 에러 (stderr) 메시지

books.cpp: In function 'll minimum_walk(std::vector<int>, int)':
books.cpp:43:22: warning: statement has no effect [-Wunused-value]
   43 |   #define debug(...) 1337
      |                      ^~~~
books.cpp:136:3: note: in expansion of macro 'debug'
  136 |   debug(comp);
      |   ^~~~~
books.cpp:43:22: warning: statement has no effect [-Wunused-value]
   43 |   #define debug(...) 1337
      |                      ^~~~
books.cpp:147:7: note: in expansion of macro 'debug'
  147 |       debug(c, comp[i], dist);
      |       ^~~~~
books.cpp:43:22: warning: statement has no effect [-Wunused-value]
   43 |   #define debug(...) 1337
      |                      ^~~~
books.cpp:170:3: note: in expansion of macro 'debug'
  170 |   debug(dist);
      |   ^~~~~
books.cpp:43:22: warning: statement has no effect [-Wunused-value]
   43 |   #define debug(...) 1337
      |                      ^~~~
books.cpp:171:3: note: in expansion of macro 'debug'
  171 |   debug(par_w);
      |   ^~~~~
#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...