#include "testlib.h" #include using namespace std; int n; // This function reads a heap from the given stream, checks it's a valid max‐heap permutation, // simulates the heap‐sort delete‐max phase, counts the number of swaps, and returns it. // On invalid heap it quits with _wa if stream==ouf, or _fail if stream==ans. long long readAns(InStream &stream) { // Read the heap permutation vector a(n+1); vector used(n+1, 0); for (int i = 1; i <= n; i++) { a[i] = stream.readInt(1, n, format("a[%d]", i).c_str()); if (used[a[i]]) { stream.quitf(_wa, "value %d appears more than once", a[i]); } used[a[i]] = 1; } // Check it's a max-heap: for all i>1, a[parent] >= a[i] for (int i = 2; i <= n; i++) { int p = i / 2; if (a[p] < a[i]) { stream.quitf(_wa, "heap property violated at index %d: parent a[%d]=%d < a[%d]=%d", i, p, a[p], i, a[i]); } } // Simulate heap-sort delete-max phase and count swaps long long swaps = 0; // make a working copy vector h = a; int sz = n; while (sz > 1) { // swap root with last swaps++; std::swap(h[1], h[sz]); sz--; // sift-down from 1 int v = 1; while (true) { int l = v * 2; int r = v * 2 + 1; if (l > sz) break; int c = l; if (r <= sz && h[r] > h[l]) c = r; if (h[v] < h[c]) { swaps++; std::swap(h[v], h[c]); v = c; } else { break; } } } return swaps; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); n = inf.readInt(); // input n // Read jury's and participant's answer swap counts long long jans = readAns(ans); long long pans = readAns(ouf); if (jans > pans) { quitf(_wa, "too few swaps: expected %lld, found %lld", jans, pans); } else if (jans < pans) { quitf(_fail, "participant has more swaps than jury: jury=%lld, participant=%lld", jans, pans); } else { quitf(_ok, "swaps = %lld", pans); } return 0; }

코드 #5756