QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#669244 | #7719. Drawing Lines | ucup-team173 | TL | 38ms | 3956kb | C++20 | 6.4kb | 2024-10-23 17:52:08 | 2024-10-23 17:52:11 |
Judging History
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 ...