QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#202946#7114. Best Interactive Playersiro53AC ✓1ms3564kbC++172.6kb2023-10-06 14:15:552023-10-06 14:15:55

Judging History

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

  • [2023-10-06 14:15:55]
  • 评测
  • 测评结果:AC
  • 用时:1ms
  • 内存:3564kb
  • [2023-10-06 14:15:55]
  • 提交

answer

#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
template <class T> inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T> inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return 1;
    }
    return 0;
}
#ifdef DEBUG
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
    os << '(' << p.first << ',' << p.second << ')';
    return os;
}
template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
    os << '{';
    for(int i = 0; i < (int)v.size(); i++) {
        if(i) { os << ','; }
        os << v[i];
    }
    os << '}';
    return os;
}
void debugg() { cerr << endl; }
template <class T, class... Args>
void debugg(const T &x, const Args &... args) {
    cerr << " " << x;
    debugg(args...);
}
#define debug(...)                                                             \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]: ", debugg(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

struct Setup {
    Setup() {
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(15);
    }
} __Setup;

using ll = long long;
#define OVERLOAD3(_1, _2, _3, name, ...) name
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define REP1(i, n) for(int i = 0; i < int(n); i++)
#define REP2(i, a, b) for(int i = (a); i < int(b); i++)
#define REP(...) OVERLOAD3(__VA_ARGS__, REP2, REP1)(__VA_ARGS__)
#define UNIQUE(v) sort(ALL(v)), (v).erase(unique(ALL(v)), (v).end())
#define REVERSE(v) reverse(ALL(v))
#define SZ(v) ((int)(v).size())
const int INF = 1 << 30;
const ll LLINF = 1LL << 60;
constexpr int MOD = 1000000007;
constexpr int MOD2 = 998244353;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

void Case(int i) { cout << "Case #" << i << ": "; }
int popcount(int x) { return __builtin_popcount(x); }
ll popcount(ll x) { return __builtin_popcountll(x); }
#pragma endregion Macros

int ask(int x) {
    cout << "? " << x << endl;
    int res;
    cin >> res;
    return res;
}
void answer(int x) {
    cout << "! " << x << endl;
    exit(0);
}

int main() {
    if(ask(1000000000) == 0) {
        answer(1000000000);
    }
    int ok = 1000000000, ng = 1;
    while(ok - ng > 1) {
        int mid = (ok + ng) / 2;
        (ask(mid) ? ok : ng) = mid;
    }
    answer(ok - 1);
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3392kb

input:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0
0

output:

? 1000000000
? 500000000
? 250000000
? 125000000
? 62500000
? 31250000
? 15625000
? 7812500
? 3906250
? 1953125
? 976563
? 488282
? 244141
? 122071
? 61036
? 30518
? 15259
? 7630
? 3815
? 1908
? 954
? 477
? 239
? 120
? 60
? 30
? 15
? 8
? 4
? 2
? 3
! 3

result:

ok ok

Test #2:

score: 0
Accepted
time: 1ms
memory: 3552kb

input:

1
1
1
0
0
0
1
1
1
0
0
1
1
1
1
1
1
1
0
0
0
0
0
1
1
1
0
1
0
1
1

output:

? 1000000000
? 500000000
? 250000000
? 125000000
? 187500000
? 218750000
? 234375000
? 226562500
? 222656250
? 220703125
? 221679687
? 222167968
? 221923827
? 221801757
? 221740722
? 221710204
? 221694945
? 221687316
? 221683501
? 221685408
? 221686362
? 221686839
? 221687077
? 221687196
? 221687136...

result:

ok ok

Test #3:

score: 0
Accepted
time: 0ms
memory: 3396kb

input:

1
1
0
0
1
1
0
0
1
1
0
1
0
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
1

output:

? 1000000000
? 500000000
? 250000000
? 375000000
? 437500000
? 406250000
? 390625000
? 398437500
? 402343750
? 400390625
? 399414062
? 399902343
? 399658202
? 399780272
? 399719237
? 399749754
? 399765013
? 399772642
? 399768827
? 399770734
? 399769780
? 399770257
? 399770495
? 399770614
? 399770554...

result:

ok ok

Test #4:

score: 0
Accepted
time: 0ms
memory: 3436kb

input:

1
1
0
1
1
0
1
1
1
1
0
0
1
0
1
0
0
1
0
1
1
1
1
0
1
1
0
0
1
0
0

output:

? 1000000000
? 500000000
? 250000000
? 375000000
? 312500000
? 281250000
? 296875000
? 289062500
? 285156250
? 283203125
? 282226562
? 282714843
? 282958984
? 282836913
? 282897948
? 282867430
? 282882689
? 282890318
? 282886503
? 282888410
? 282887456
? 282886979
? 282886741
? 282886622
? 282886681...

result:

ok ok

Test #5:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

1
1
0
0
0
1
0
0
1
1
1
1
1
1
1
0
1
1
1
0
1
1
1
0
1
1
0
0
0
0
1

output:

? 1000000000
? 500000000
? 250000000
? 375000000
? 437500000
? 468750000
? 453125000
? 460937500
? 464843750
? 462890625
? 461914062
? 461425781
? 461181640
? 461059570
? 460998535
? 460968017
? 460983276
? 460975646
? 460971831
? 460969924
? 460970877
? 460970400
? 460970162
? 460970043
? 460970102...

result:

ok ok

Test #6:

score: 0
Accepted
time: 1ms
memory: 3372kb

input:

1
0
1
0
1
1
1
0
0
0
1
1
0
0
1
1
0
1
1
1
1
1
1
0
1
0
1
1
0
1
1

output:

? 1000000000
? 500000000
? 750000000
? 625000000
? 687500000
? 656250000
? 640625000
? 632812500
? 636718750
? 638671875
? 639648437
? 639160156
? 638916015
? 639038085
? 639099120
? 639068602
? 639053343
? 639060972
? 639057157
? 639055250
? 639054296
? 639053819
? 639053581
? 639053462
? 639053521...

result:

ok ok

Test #7:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

1
0
0
1
0
1
1
1
0
1
1
0
1
0
0
0
0
0
0
0
1
1
1
0
1
0
1
0
1
1
1

output:

? 1000000000
? 500000000
? 750000000
? 875000000
? 812500000
? 843750000
? 828125000
? 820312500
? 816406250
? 818359375
? 817382812
? 816894531
? 817138671
? 817016601
? 817077636
? 817108153
? 817123412
? 817131041
? 817134856
? 817136763
? 817137717
? 817137240
? 817137001
? 817136882
? 817136941...

result:

ok ok

Test #8:

score: 0
Accepted
time: 1ms
memory: 3336kb

input:

1
0
1
0
0
1
1
0
0
1
0
1
1
1
1
0
0
0
0
1
1
0
1
1
1
0
1
0
1
0
1

output:

? 1000000000
? 500000000
? 750000000
? 625000000
? 687500000
? 718750000
? 703125000
? 695312500
? 699218750
? 701171875
? 700195312
? 700683593
? 700439452
? 700317382
? 700256347
? 700225829
? 700241088
? 700248717
? 700252532
? 700254439
? 700253485
? 700253008
? 700253246
? 700253127
? 700253067...

result:

ok ok

Test #9:

score: 0
Accepted
time: 1ms
memory: 3436kb

input:

1
0
0
1
0
0
1
1
1
1
0
1
0
0
0
0
0
1
1
1
0
1
0
1
1
1
0
0
1
0
1

output:

? 1000000000
? 500000000
? 750000000
? 875000000
? 812500000
? 843750000
? 859375000
? 851562500
? 847656250
? 845703125
? 844726562
? 845214843
? 844970702
? 845092772
? 845153807
? 845184325
? 845199584
? 845207213
? 845203398
? 845201491
? 845200537
? 845201014
? 845200775
? 845200894
? 845200834...

result:

ok ok

Test #10:

score: 0
Accepted
time: 0ms
memory: 3556kb

input:

1
0
0
0
1
1
1
1
1
1
0
0
1
1
0
1
1
0
0
1
0
0
1
1
1
0
1
1
1
1

output:

? 1000000000
? 500000000
? 750000000
? 875000000
? 937500000
? 906250000
? 890625000
? 882812500
? 878906250
? 876953125
? 875976562
? 876464843
? 876708984
? 876586913
? 876525878
? 876556395
? 876541136
? 876533507
? 876537321
? 876539228
? 876538274
? 876538751
? 876538989
? 876538870
? 876538810...

result:

ok ok

Test #11:

score: 0
Accepted
time: 0ms
memory: 3564kb

input:

0

output:

? 1000000000
! 1000000000

result:

ok ok

Test #12:

score: 0
Accepted
time: 1ms
memory: 3444kb

input:

1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1

output:

? 1000000000
? 500000000
? 250000000
? 125000000
? 62500000
? 31250000
? 15625000
? 7812500
? 3906250
? 1953125
? 976563
? 488282
? 244141
? 122071
? 61036
? 30518
? 15259
? 7630
? 3815
? 1908
? 954
? 477
? 239
? 120
? 60
? 30
? 15
? 8
? 4
? 2
! 1

result:

ok ok