#include "testlib.h" #include #include #include using namespace std; int V, P; long long L; vector villages; // Read an answer (jury or participant), validate it, compute its cost. // On invalid output: if stream == ouf -> _wa, if stream == ans -> _fail. long long readAns(InStream &stream) { // Read P positions vector offices; offices.reserve(P); // Use a multiset-like map to ensure we don't pick a village more times than it exists map cnt; for (auto x : villages) cnt[x]++; for (int i = 0; i < P; i++) { long long x = stream.readLong(0, L-1, format("position[%d]", i+1).c_str()); // Check available in input villages if (cnt[x] <= 0) { stream.quitf(_wa, "position %lld is not a valid unused village location", x); } cnt[x]--; offices.push_back(x); } // Check non-decreasing order (as per output requirement) for (int i = 1; i < P; i++) { if (offices[i] < offices[i-1]) { stream.quitf(_wa, "positions are not sorted in non-decreasing order"); } } // Compute sum of distances long long total = 0; for (int i = 0; i < V; i++) { long long x = villages[i]; long long best = L; // max possible > any real distance for (int j = 0; j < P; j++) { long long d = llabs(x - offices[j]); d = min(d, L - d); if (d < best) best = d; } total += best; } return total; } int main(int argc, char *argv[]) { registerTestlibCmd(argc, argv); // Read input V = inf.readInt(); P = inf.readInt(); L = inf.readLong(); villages.resize(V); for (int i = 0; i < V; i++) { villages[i] = inf.readLong(0, L-1); } long long juryCost = readAns(ans); long long partCost = readAns(ouf); if (partCost > juryCost) { quitf(_wa, "participant cost %lld is worse than jury cost %lld", partCost, juryCost); } else if (partCost < juryCost) { // Participant found a better solution than jury: indicates jury data is wrong quitf(_fail, "participant cost %lld is better than jury cost %lld", partCost, juryCost); } else { quitf(_ok, "cost = %lld", partCost); } return 0; }

코드 #5810