QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#103746	#6394. Turn on the Light	rniya	AC ✓	5ms	3508kb	C++17	1.9kb	2023-05-07 14:12:47	2023-05-07 14:12:51

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-05-07 14:12:51]
评测

测评结果：AC
用时：5ms
内存：3508kb

查看

[2023-05-07 14:12:47]
提交

answer

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.hpp>
#else
#define debug(...) void(0)
#endif

using namespace std;

typedef long long ll;
#define all(x) begin(x), end(x)
constexpr int INF = (1 << 30) - 1;
constexpr long long IINF = (1LL << 60) - 1;
constexpr int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

template <class T> istream& operator>>(istream& is, vector<T>& v) {
    for (auto& x : v) is >> x;
    return is;
}

template <class T> ostream& operator<<(ostream& os, const vector<T>& v) {
    auto sep = "";
    for (const auto& x : v) os << exchange(sep, " ") << x;
    return os;
}

template <class T, class U = T> bool chmin(T& x, U&& y) { return y < x and (x = forward<U>(y), true); }

template <class T, class U = T> bool chmax(T& x, U&& y) { return x < y and (x = forward<U>(y), true); }

template <class T> void mkuni(vector<T>& v) {
    sort(begin(v), end(v));
    v.erase(unique(begin(v), end(v)), end(v));
}

template <class T> int lwb(const vector<T>& v, const T& x) { return lower_bound(begin(v), end(v), x) - begin(v); }

int n;

int query(int x) {
    assert(0 <= x and x < n);
    cout << "? " << x + 1 << endl;
    int res;
    cin >> res;
    return res;
}

void answer(int x) {
    assert(0 <= x and x < n);
    cout << "! " << x + 1 << endl;
    exit(0);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int lb = 0, ub = n, L = 0, R = 0, res;
    while (ub - lb > 1) {
        int mid = (lb + ub) >> 1;
        res = query(mid);
        if (res == abs(L - R)) answer(mid);
        if (mid == ub - 1) answer(lb);
        res = query(ub - 1);
        if (res == abs(L + 1 - R)) answer(ub - 1);
        if (res == abs(L - (R + 2))) {
            ub = mid;
            R += 2;
        } else {
            assert(res == abs(L - R));
            lb = mid + 1;
            ub--;
            L++, R++;
        }
    }
    answer(lb);
    return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 1ms

memory: 3444kb

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #2:

score: 0

Accepted

time: 2ms

memory: 3332kb

input:

output:

? 6
? 10
? 3
? 5
? 2
! 1

result:

ok Correct position at 1

Test #3:

score: 0

Accepted

time: 3ms

memory: 3388kb

input:

output:

? 5
? 9
? 3
? 4
? 2
! 1

result:

ok Correct position at 1

Test #4:

score: 0

Accepted

time: 2ms

memory: 3460kb

input:

output:

? 5
? 8
? 3
? 4
? 2
! 1

result:

ok Correct position at 1

Test #5:

score: 0

Accepted

time: 2ms

memory: 3260kb

input:

output:

? 4
? 7
? 2
? 3
! 1

result:

ok Correct position at 1

Test #6:

score: 0

Accepted

time: 2ms

memory: 3340kb

input:

output:

? 4
? 6
? 2
? 3
! 1

result:

ok Correct position at 1

Test #7:

score: 0

Accepted

time: 1ms

memory: 3444kb

input:

output:

? 3
? 5
? 2
! 1

result:

ok Correct position at 1

Test #8:

score: 0

Accepted

time: 2ms

memory: 3392kb

input:

output:

? 3
? 4
? 2
! 1

result:

ok Correct position at 1

Test #9:

score: 0

Accepted

time: 2ms

memory: 3340kb

input:

3
1
1

output:

? 2
? 3
! 3

result:

ok Correct position at 3

Test #10:

score: 0

Accepted

time: 1ms

memory: 3440kb

input:

2
1

output:

? 2
! 1

result:

ok Correct position at 1

Test #11:

score: 0

Accepted

time: 2ms

memory: 3300kb

input:

output:

! 1

result:

ok Correct position at 1

Test #12:

score: 0

Accepted

time: 1ms

memory: 3492kb

input:

output:

result:

ok Correct position at 9

Test #13:

score: 0

Accepted

time: 4ms

memory: 3296kb

input:

output:

result:

ok Correct position at 82040

Test #14:

score: 0

Accepted

time: 5ms

memory: 3332kb

input:

output:

result:

ok Correct position at 82040

Test #15:

score: 0

Accepted

time: 4ms

memory: 3444kb

input:

output:

result:

ok Correct position at 82040

Test #16:

score: 0

Accepted

time: 4ms

memory: 3340kb

input:

output:

result:

ok Correct position at 82040

Test #17:

score: 0

Accepted

time: 0ms

memory: 3260kb

input:

output:

result:

ok Correct position at 82040

Test #18:

score: 0

Accepted

time: 0ms

memory: 3396kb

input:

output:

result:

ok Correct position at 82040

Test #19:

score: 0

Accepted

time: 5ms

memory: 3304kb

input:

output:

result:

ok Correct position at 82040

Test #20:

score: 0

Accepted

time: 2ms

memory: 3456kb

input:

output:

result:

ok Correct position at 82040

Test #21:

score: 0

Accepted

time: 2ms

memory: 3400kb

input:

output:

result:

ok Correct position at 31259

Test #22:

score: 0

Accepted

time: 4ms

memory: 3508kb

input:

output:

result:

ok Correct position at 43

Test #23:

score: 0

Accepted

time: 1ms

memory: 3304kb

input:

output:

result:

ok Correct position at 51

Test #24:

score: 0

Accepted

time: 4ms

memory: 3440kb

input:

output:

result:

ok Correct position at 51

Test #25:

score: 0

Accepted

time: 1ms

memory: 3440kb

input:

output:

result:

ok Correct position at 51

Test #26:

score: 0

Accepted

time: 2ms

memory: 3344kb

input:

output:

result:

ok Correct position at 999781

Test #27:

score: 0

Accepted

time: 4ms

memory: 3348kb

input:

output:

result:

ok Correct position at 999980

Test #28:

score: 0

Accepted

time: 1ms

memory: 3488kb

input:

output:

result:

ok Correct position at 999979

Test #29:

score: 0

Accepted

time: 1ms

memory: 3264kb

input:

output:

result:

ok Correct position at 999978

Test #30:

score: 0

Accepted

time: 4ms

memory: 3340kb

input:

output:

result:

ok Correct position at 499947

Test #31:

score: 0

Accepted

time: 4ms

memory: 3492kb

input:

output:

result:

ok Correct position at 500070

Test #32:

score: 0

Accepted

time: 3ms

memory: 3400kb

input:

output:

result:

ok Correct position at 500076

Test #33:

score: 0

Accepted

time: 4ms

memory: 3336kb

input:

output:

result:

ok Correct position at 499965

Test #34:

score: 0

Accepted

time: 5ms

memory: 3348kb

input:

output:

result:

ok Correct position at 11777

Test #35:

score: 0

Accepted

time: 0ms

memory: 3300kb

input:

output:

result:

ok Correct position at 339207

Test #36:

score: 0

Accepted

time: 0ms

memory: 3492kb

input:

output:

result:

ok Correct position at 339207

Test #37:

score: 0

Accepted

time: 4ms

memory: 3508kb

input:

output:

result:

ok Correct position at 157848

Test #38:

score: 0

Accepted

time: 5ms

memory: 3336kb

input:

output:

result:

ok Correct position at 1

Test #39:

score: 0

Accepted

time: 3ms

memory: 3300kb

input:

output:

result:

ok Correct position at 1

Test #40:

score: 0

Accepted

time: 1ms

memory: 3332kb

input:

output:

result:

ok Correct position at 1

Test #41:

score: 0

Accepted

time: 5ms

memory: 3396kb

input:

output:

result:

ok Correct position at 1

Test #42:

score: 0

Accepted

time: 2ms

memory: 3304kb

input:

1000000
1
1

output:

? 500001
? 1000000
! 1000000

result:

ok Correct position at 1000000

Test #43:

score: 0

Accepted

time: 1ms

memory: 3300kb

input:

output:

result:

ok Correct position at 1