QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#797439#9818. Hash Collisionucup-team004WA 1ms3844kbC++231.2kb2024-12-03 00:06:252024-12-03 00:06:34

Judging History

This is the latest submission verdict.

  • [2024-12-03 00:06:34]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 3844kb
  • [2024-12-03 00:06:25]
  • Submitted

answer

#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;
using u128 = unsigned __int128;

constexpr int B = std::sqrt(200000);

int query(int c, int r) {
    std::cout << "? " << c << " " << r << std::endl;
    int ans;
    std::cin >> ans;
    return ans;
}

int getlen(int n, int s) {
    std::vector<int> f {s};
    std::vector<int> id(n + 1, -1);
    for (int i = 1; i < B; i++) {
        int x = query(i, s);
        if (x == n) {
            return i;
        }
        f.push_back(x);
    }
    for (int i = 0; i < B; i++) {
        id[f[i]] = i;
    }
    int i;
    for (i = B; ; i += B) {
        int x;
        if (i <= n) {
            x = query(i, s);
        } else {
            x = query(n, s);
            x = query(i - n, x);
        }
        if (id[x] != -1) {
            return i - id[x];
        }
    }
    assert(false);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;
    
    int s = query(n, 1);
    
    int c = getlen(n, s);
    
    int x = query(c - s % c, s);
    std::cout << "! " << s << " " << x << std::endl;
    
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 1ms
memory: 3844kb

input:

6
2
3
5
4
2
3
5

output:

? 6 1
? 1 2
? 2 2
? 3 2
? 4 2
? 5 2
? 6 2
? 7 2

result:

wrong answer Integer parameter [name=c] equals to 7, violates the range [1, 6]