Submission #1072634

#TimeUsernameProblemLanguageResultExecution timeMemory
1072634That_SalamanderMinerals (JOI19_minerals)C++17
80 / 100
32 ms2968 KiB
#include <bits/stdc++.h> void Solve(int N); int Query(int x); void Answer(int x, int y); bool inMachine[100005]; int lastRes = 0; int opCount = 0; void setInMachine(int i, bool val) { if (inMachine[i] != val) { lastRes = Query(i); opCount++; inMachine[i] = val; } } void flip(int i) { setInMachine(i, !inMachine[i]); } int query() { return lastRes; } void findMatching(std::vector<int>& a, std::vector<int>& b) { if (a.size() == 1) { Answer(a[0], b[0]); return; } std::vector<int> a1, a2, b1, b2; for (int i = 0; i < a.size(); i++) { if (i % 2) { a2.push_back(a[i]); } else { a1.push_back(a[i]); } } for (int x: a1) { setInMachine(x, false); } for (int x: a2) { setInMachine(x, true); } for (int x: b) { int prev = query(); flip(x); if (prev != query()) { b1.push_back(x); } else { b2.push_back(x); } } //std::cout << a1.size() << " " << b1.size() << std::endl; findMatching(a1, b1); findMatching(a2, b2); } void Solve(int N) { lastRes = 0; opCount = 0; memset(inMachine, 0, sizeof(inMachine)); std::vector<int> a, b; for (int i = 1; i <= 2 * N; i++) { int prev = query(); flip(i); if (prev == query()) { b.push_back(i); } else { a.push_back(i); } } findMatching(a, b); } #ifdef LOCAL_TEST #include <cstdio> #include <cstdlib> #include <algorithm> constexpr int MAX_N = 43000; constexpr int MAX_CALLS = 1000000; namespace { void WrongAnswer(int code) { printf("Wrong Answer [%d]\n", code); exit(0); } int N; int counterpart[2 * MAX_N + 1]; int num_queries; int num_kinds; int on[2 * MAX_N + 1]; int count[2 * MAX_N + 1]; int num_answers; int answer[2 * MAX_N + 1]; } // namespace int Query(int x) { if (!(1 <= x && x <= 2 * N)) { printf("Query(%d)\n", x); WrongAnswer(1); } if (++num_queries > MAX_CALLS) { //WrongAnswer(2); } const int type = std::min(x, counterpart[x]); if (on[x]) { --on[x]; --count[type]; if (count[type] == 0) { --num_kinds; } } else { ++on[x]; ++count[type]; if (count[type] == 1) { ++num_kinds; } } return num_kinds; } void Answer(int a, int b) { if (N < 100) std::cout << "Answer(" << a << ", " << b << ")" << std::endl; if (++num_answers > N) { WrongAnswer(6); } if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) { WrongAnswer(3); } if (answer[a] != 0) { WrongAnswer(4); } answer[a] = b; if (answer[b] != 0) { WrongAnswer(4); } answer[b] = a; if (!(counterpart[a] == b && counterpart[b] == a)) { WrongAnswer(5); } } int secret_order[100000]; int main() { if (scanf("%d", &N) != 1) { fprintf(stderr, "Error while reading input\n"); exit(1); } for (int i = 0; i < 2 * N; ++i) { secret_order[i] = i + 1; } std::random_device rd; std::mt19937 rng(rd()); int maxQueries = 0; for (int iter = 0; iter < 100; iter++) { num_queries = 0; num_kinds = 0; memset(on, 0, sizeof(on)); memset(count, 0, sizeof(count)); num_answers = 0; memset(answer, 0, sizeof(answer)); memset(counterpart, 0, sizeof(counterpart)); std::shuffle(secret_order, secret_order + 2 * N, rng); for (int i = 1; i <= N; ++i) { int x, y; x = secret_order[2 * i - 2]; y = secret_order[2 * i - 1]; /*if (scanf("%d%d", &x, &y) != 2) { fprintf(stderr, "Error while reading input\n"); exit(1); }*/ if (N < 100) printf("%d %d\n", x, y); counterpart[x] = y; counterpart[y] = x; } Solve(N); if (num_answers != N) { WrongAnswer(6); } printf("Accepted: %d\n", num_queries); maxQueries = std::max(maxQueries, num_queries); } std::cout << "Max queries: " << maxQueries << std::endl; return 0; } #endif

Compilation message (stderr)

minerals.cpp: In function 'void findMatching(std::vector<int>&, std::vector<int>&)':
minerals.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i < a.size(); i++) {
      |                     ~~^~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...