QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#669244#7719. Drawing Linesucup-team173TL 38ms3956kbC++206.4kb2024-10-23 17:52:082024-10-23 17:52:11

Judging History

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

  • [2024-10-23 17:52:11]
  • 评测
  • 测评结果:TL
  • 用时:38ms
  • 内存:3956kb
  • [2024-10-23 17:52:08]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int lim = 1e4;
mt19937_64 rng(time(0));
ll get(ll l, ll r) {
    return uniform_int_distribution<ll>(l, r)(rng);
}
int valid(int x) {
    return -lim <= x && x <= lim;
}
// #define local114514

double dst(int a1, int b1, int a2, int b2) {
    return sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2));
}

int A=get(-lim,lim);
int B=get(-lim,lim);
int C=get(-lim,lim);
int D=get(-lim,lim);
double ask(int x1, int y1, int x2, int y2) {
#ifdef local114514
    int X1 = A, Y1 = B;
    int X2 = C, Y2 = D;
    double d1 = dst(x1, y1, X1, Y1) + dst(x2, y2, X2, Y2);
    double d2 = dst(x1, y1, X2, Y2) + dst(x2, y2, X1, Y1);
    double s = min(d1, d2);
    double res;
    if (s == 0)
        res = 100.;
    else {
        double sim = max(0., (40000 - s) / 40000);
        res = (int)(sim * 1000) / 10.;
    }
    static int cnt = 0;
    // assert(valid(x1)&&valid(x2)&&valid(y1)&&valid(y2));
    cerr << ++cnt << "th qry\n";
    cerr << x1 << " " << y1 << " " << x2 << " " << y2 << " " << res << "\n";
    if(res==100.)cerr<<"holy jesus you made it\n";
#endif
#ifndef local114514
    cout << x1 << " " << y1 << " " << x2 << " " << y2 << endl;
    double res;
    cin >> res;
    if(res==100.)exit(0);
#endif
    return res;
}
void make_valid(int& x) {
    x = max(x, -lim);
    x = min(x, lim);
}

void solve() {
    // double t=20000;
    // cerr<<ask(99,99,99,99)<<"\n";
    // cerr<<ask(50,99,99,99)<<"\n";
    // cerr<<ask(50,0,-50,0)<<"\n";
    // return;

    int x1 = get(-lim, lim), y1 = get(-lim, lim);
    int x2 = get(-lim, lim), y2 = get(-lim, lim);
    int x[4] = {x1, y1, x2, y2};
    double old = ask(x1, y1, x2, y2);
    // int timer=24000;
    // int move=0;
    // while(timer--){
    //     move^=1;
    //     int range=(int)max(1.,t);
    //     cerr<<range<<" range\n";
    //     int dx=get(-range,range);
    //     int dy=get(-range,range);
    //     if(move){
    //         dx+=x1,make_valid(dx);
    //         dy+=y1,make_valid(dy);
    //         double newans=ask(dx,dy,x2,y2);
    //         cerr<<dx<<" "<<dy<<" "<<x2<<" "<<y2<<" "<<newans<<"\n";
    //         if(newans==100.)return;
    //         double delta=old-newans;
    //         if(exp(-delta/t)>get(1,1e9)/1e9){
    //             old=newans;
    //             x1=dx,y1=dy;
    //         }
    //     }
    //     else{
    //         dx+=x2,make_valid(dx);
    //         dy+=y2,make_valid(dy);
    //         double newans=ask(x1,y1,dx,dy);
    //         cerr<<x1<<" "<<x2<<" "<<dx<<" "<<dy<<" "<<newans<<"\n";
    //         if(newans==100.)return;
    //         double delta=old-newans;
    //         if(exp(-delta/t)>get(1,1e9)/1e9){
    //             old=newans;
    //             x2=dx,y2=dy;
    //         }
    //     }
    //     t*=0.9993;
    // }
    // cerr<<"fuck, GG\n";
    int change = 0;

    while (1) {
        int l = -lim, r = lim;
        int oldx = x[change];

        while (r - l >= 20) {
            int lm = (l + l + r) / 3., rm = (l + r + r) / 3.;
            x[change] = lm;
            double vl = ask(x[0], x[1], x[2], x[3]);
            if (vl == 100.) exit(0);
            x[change] = rm;
            double vr = ask(x[0], x[1], x[2], x[3]);
            if (vr == 100.) exit(0);
            if (vl > vr)
                r = rm;
            else if (vl < vr)
                l = lm;
            else if (get(0, 1e9) > 5e8)
                l = lm;
            else
                r = rm;
        }
        for (int i = l; i <= r; i++) {
            x[change] = i;
            double v = ask(x[0], x[1], x[2], x[3]);
            if (v == 100.) exit(0);
            if (v > old || (v == old && get(0, 1e9) > 5e8)) {
                oldx = i;
                old = v;
            }
        }
        x[change] = oldx;
        // cerr << x[0] << " " << x[1] << " " << x[2] << " " << x[3] << " " << old << " fuck\n";
        if (old == 99.9) break;
        change = (change + 1) % 4;
    }
    // cerr<<"ok lets go\n";
    while (1) {
        vector<int> choose(4);
        iota(choose.begin(), choose.end(), 0);
        shuffle(choose.begin(), choose.end(), rng);
        int t = choose[0], s = choose[1];
        int tmp = x[s];
        double v = ask(x[0], x[1], x[2], x[3]);
        if(v==100.)exit(0);
        // assert(v == 99.9);
        auto checkfor = [&](int xs) {
            int oldt = x[t];
            int olds = x[s];
            x[s] = xs;
            double v = ask(x[0], x[1], x[2], x[3]);
            if (v != 99.9) return 0;
            int l = 1, r = 1;
            while (valid(oldt - l)) {
                x[t] = oldt - l;
                double v = ask(x[0], x[1], x[2], x[3]);
                if (v == 100.) exit(0);
                if (v != 99.9) break;
                l++;
            }
            while (valid(oldt + r)) {
                x[t] = oldt + r;
                double v = ask(x[0], x[1], x[2], x[3]);
                if (v == 100.) exit(0);
                if (v != 99.9) break;
                r++;
            }
            x[t] = oldt;
            x[s] = olds;
            return r + l - 1;
        };
        auto getxs = [&](int delta) {
            int tmp = x[s] + delta;
            make_valid(tmp);
            return checkfor(tmp);
        };
        int mid = getxs(0);
        int o = 1, L, R;
        while (1) {
            L = getxs(-o), R = getxs(o);
            // cout<<mid<<" "<<L<<" "<<R<<"\n";
            // cerr<<"??"<<" "<<o<<"\n";
            if (L == R && L == mid) {
                o++;
                continue;
            }
            break;
        }
        // cerr<<"whatlaksjdfla\n";
        if (mid >= L && mid >= R) {
            if (L > R && L == mid)
                x[s]--, make_valid(x[s]);
            else if (L < R && R == mid)
                x[s]++, make_valid(x[s]);
        } else {
            if (L > mid)
                x[s]--, make_valid(x[s]);
            else if (R > mid)
                x[s]++, make_valid(x[s]);
            // else
            //     assert(0);
        }
        // cerr << x[0] << " " << x[1] << " " << x[2] << " " << x[3] <<  " fuck\n";
    }
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 33ms
memory: 3828kb

input:

69.6
70.5
70.5
65.2
75.3
72.2
76.2
76.0
74.8
75.0
76.3
76.2
76.1
75.9
76.3
76.2
76.3
76.3
76.2
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
76.3
70.9
70.9
65.4
76.5
72.8
78.3
77.7
75.9
76.1
...

output:

-3730 -1187 850 8239
-3333 -1187 850 8239
3333 -1187 850 8239
-5555 -1187 850 8239
-1111 -1187 850 8239
-2592 -1187 850 8239
370 -1187 850 8239
-617 -1187 850 8239
1358 -1187 850 8239
-1275 -1187 850 8239
41 -1187 850 8239
-397 -1187 850 8239
480 -1187 850 8239
-690 -1187 850 8239
-105 -1187 850 823...

result:

ok 15697 queries

Test #2:

score: 0
Accepted
time: 33ms
memory: 3832kb

input:

44.2
45.0
51.2
50.9
49.9
49.8
51.3
51.0
51.2
51.3
50.9
51.2
51.2
51.2
51.3
51.3
51.3
51.2
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
51.3
56.6
40.0
62.2
51.1
65.8
58.5
64.3
63.4
...

output:

-3730 -1187 850 8239
-3333 -1187 850 8239
3333 -1187 850 8239
1111 -1187 850 8239
5555 -1187 850 8239
-370 -1187 850 8239
2592 -1187 850 8239
1605 -1187 850 8239
3580 -1187 850 8239
2921 -1187 850 8239
4238 -1187 850 8239
2482 -1187 850 8239
3360 -1187 850 8239
2190 -1187 850 8239
2775 -1187 850 823...

result:

ok 7796 queries

Test #3:

score: 0
Accepted
time: 18ms
memory: 3788kb

input:

70.2
68.8
73.4
75.9
69.8
74.7
74.7
73.0
75.8
75.2
75.9
75.8
75.7
75.7
75.9
75.9
75.9
75.8
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
75.9
74.1
71.4
71.5
79.6
75.9
78.8
80.7
76.3
...

output:

-2721 1527 346 -4963
-3333 1527 346 -4963
3333 1527 346 -4963
1111 1527 346 -4963
5555 1527 346 -4963
-370 1527 346 -4963
2592 1527 346 -4963
-1358 1527 346 -4963
617 1527 346 -4963
-41 1527 346 -4963
1275 1527 346 -4963
836 1527 346 -4963
1714 1527 346 -4963
544 1527 346 -4963
1129 1527 346 -4963
9...

result:

ok 11604 queries

Test #4:

score: 0
Accepted
time: 15ms
memory: 3956kb

input:

72.4
72.0
69.5
69.4
73.0
72.5
72.6
72.9
71.9
73.0
72.7
72.9
73.0
73.0
72.9
73.0
73.0
72.9
73.0
73.0
73.0
73.0
73.0
72.9
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
73.0
60.8
77.5
71.9
83.0
79.3
86.6
84.2
88.0
...

output:

-2721 1527 346 -4963
-3333 1527 346 -4963
3333 1527 346 -4963
-5555 1527 346 -4963
-1111 1527 346 -4963
-2592 1527 346 -4963
370 1527 346 -4963
-617 1527 346 -4963
1358 1527 346 -4963
-1275 1527 346 -4963
41 1527 346 -4963
-1714 1527 346 -4963
-836 1527 346 -4963
-1129 1527 346 -4963
-544 1527 346 -...

result:

ok 9202 queries

Test #5:

score: 0
Accepted
time: 21ms
memory: 3812kb

input:

68.8
67.5
77.8
75.8
77.2
77.9
75.5
77.7
77.6
77.3
77.9
77.8
77.9
77.9
77.8
77.9
77.9
77.9
77.9
77.9
77.9
77.8
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
77.9
86.9
73.4
81.7
84.4
87.5
80.7
86.4
85.6
84.9
...

output:

-2721 1527 346 -4963
-3333 1527 346 -4963
3333 1527 346 -4963
1111 1527 346 -4963
5555 1527 346 -4963
4074 1527 346 -4963
7037 1527 346 -4963
3086 1527 346 -4963
5061 1527 346 -4963
2427 1527 346 -4963
3744 1527 346 -4963
3305 1527 346 -4963
4183 1527 346 -4963
3890 1527 346 -4963
4475 1527 346 -496...

result:

ok 10222 queries

Test #6:

score: 0
Accepted
time: 5ms
memory: 3812kb

input:

55.2
85.7
71.5
80.5
82.5
85.9
78.9
85.2
83.7
83.7
86.2
85.7
85.7
86.1
85.1
86.2
85.9
86.1
86.2
86.2
86.1
86.2
86.2
86.1
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
86.2
85.9
69.3
82.8
80.4
79.1
86.5
84.0
85.3
87.0
...

output:

9841 -4205 -2144 -9087
-3333 -4205 -2144 -9087
3333 -4205 -2144 -9087
-5555 -4205 -2144 -9087
-1111 -4205 -2144 -9087
-2592 -4205 -2144 -9087
370 -4205 -2144 -9087
-3580 -4205 -2144 -9087
-1605 -4205 -2144 -9087
-4238 -4205 -2144 -9087
-2921 -4205 -2144 -9087
-3360 -4205 -2144 -9087
-2482 -4205 -214...

result:

ok 3623 queries

Test #7:

score: 0
Accepted
time: 38ms
memory: 3788kb

input:

44.2
54.2
54.8
56.3
52.0
56.3
55.5
55.9
56.4
56.4
56.2
56.3
56.4
56.4
56.4
56.4
56.3
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
56.4
58.6
72.1
69.7
66.6
66.0
73.2
70.9
71.5
73.1
...

output:

9841 -4205 -2144 -9087
-3333 -4205 -2144 -9087
3333 -4205 -2144 -9087
1111 -4205 -2144 -9087
5555 -4205 -2144 -9087
-370 -4205 -2144 -9087
2592 -4205 -2144 -9087
-1358 -4205 -2144 -9087
617 -4205 -2144 -9087
-41 -4205 -2144 -9087
1275 -4205 -2144 -9087
-480 -4205 -2144 -9087
397 -4205 -2144 -9087
10...

result:

ok 16056 queries

Test #8:

score: -100
Time Limit Exceeded

input:

62.3
60.6
65.7
64.9
65.5
65.8
64.8
65.7
65.6
65.5
65.7
65.7
65.7
65.8
65.7
65.7
65.8
65.8
65.7
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
65.8
67.9
84.6
79.0
90.2
86.5
93.9
91.4
94.5
...

output:

9841 -4205 -2144 -9087
-3333 -4205 -2144 -9087
3333 -4205 -2144 -9087
1111 -4205 -2144 -9087
5555 -4205 -2144 -9087
4074 -4205 -2144 -9087
7037 -4205 -2144 -9087
3086 -4205 -2144 -9087
5061 -4205 -2144 -9087
2427 -4205 -2144 -9087
3744 -4205 -2144 -9087
3305 -4205 -2144 -9087
4183 -4205 -2144 -9087
...

result: