QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#584235 | #8270. Mineral deposits | hansiyuan | 9 | 7ms | 4276kb | C++14 | 2.0kb | 2024-09-23 10:41:25 | 2024-09-23 10:41:25 |
answer
#include <bits/stdc++.h>
#define pii pair<int,int>
#define X first
#define Y second
using namespace std;
const int bor = 1e8;
int b,k,w,d;
int D[100];
set<pii> ta;
vector<pii> a;
set<int> s,key;
vector<pii> ques;
multiset<int> res;
int dis[405];
int Dis(pii u,pii v){
return abs(u.X-v.X)+abs(u.Y-v.Y);
}
bool chk(int i,int dx,int dy){
pii u = a[i];
pii p = {u.X+dx,u.Y+dy};
int dt = Dis(u,p);
if(p.X < -bor || p.X > bor || p.Y < -bor || p.Y > bor) return false;
for(int j=i+1;j<a.size();j++){
pii v = a[j];
if(key.count(Dis(v,p)) || Dis(v,p)==dt) return false;
}
//printf("%d %d\n",p.X,p.Y);
key.insert(dt);
for(int i=0;i<a.size();i++)
s.insert(Dis(a[i],p));
ques.push_back(p);
return true;
}
int main(){
scanf("%d%d%d",&b,&k,&w);
printf("? %d %d %d %d\n",-b,-b,-b,b);
fflush(stdout);
for(int i=1;i<=k*2;i++)
scanf("%d",&D[i]);
for(int i=1;i<=k*2;i++)
for(int j=1;j<=k*2;j++){
ta.insert({(D[i]+D[j])/2-b*2,(D[i]-D[j])/2});
}
while(ta.size()){
pii p = *ta.begin();
ta.erase(p);
if(p.X < -b || p.X > b || p.Y < -b || p.Y > b) continue;
a.push_back(p);
// printf("%d %d\n",p.X,p.Y);
}
for(int i=0;i<a.size();i++){
pii p = a[i];
while(!chk(i,-d,0) && !chk(i,d,0) && !chk(i,0,-d) && !chk(i,0,d)) d++;
dis[i] = d;
while(s.count(d)) d++;
}
printf("? ");
for(pii p:ques) printf("%d %d ",p.X,p.Y);
puts(""); fflush(stdout);
for(int i=1;i<=ques.size()*k;i++){
int x; scanf("%d",&x);
res.insert(x);
}
printf("! ");
for(int i=0;i<a.size();i++){
pii u = a[i];
if(res.find(dis[i])!=res.end()){
printf("%d %d ",u.X,u.Y);
for(pii q:ques){
res.erase(Dis(u,q));
}
}
}
fflush(stdout);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 9
Accepted
Test #1:
score: 9
Accepted
time: 1ms
memory: 3756kb
input:
10 1 10000 20 30 2 7 10 11
output:
? -10 -10 -10 10 ? 0 0 4 -5 3 5 7 0 ! 5 5
result:
ok correct answer
Test #2:
score: 9
Accepted
time: 0ms
memory: 3816kb
input:
10 1 10000 28 30 2 3 4 5
output:
? -10 -10 -10 10 ? 8 0 8 -1 5 1 5 0 ! 9 1
result:
ok correct answer
Test #3:
score: 9
Accepted
time: 1ms
memory: 3792kb
input:
10 1 10000 13 29 2 13 16 17
output:
? -10 -10 -10 10 ? -7 0 0 -8 -1 8 6 0 ! 1 8
result:
ok correct answer
Test #4:
score: 9
Accepted
time: 0ms
memory: 3872kb
input:
10 1 10000 20 20 0
output:
? -10 -10 -10 10 ? 0 0 ! 0 0
result:
ok correct answer
Test #5:
score: 9
Accepted
time: 1ms
memory: 3864kb
input:
10 1 10000 30 30 0
output:
? -10 -10 -10 10 ? 10 0 ! 10 0
result:
ok correct answer
Test #6:
score: 9
Accepted
time: 0ms
memory: 3816kb
input:
10 1 10000 10 30 2 17 20 21
output:
? -10 -10 -10 10 ? -10 0 -1 -10 -2 10 7 0 ! 0 10
result:
ok correct answer
Test #7:
score: 9
Accepted
time: 1ms
memory: 3792kb
input:
10 1 10000 20 40 2 20 21
output:
? -10 -10 -10 10 ? 0 0 9 -10 8 10 ! 10 10
result:
ok correct answer
Test #8:
score: 9
Accepted
time: 1ms
memory: 3944kb
input:
100000000 1 10000 165772754 332220904 1 166448150 166448152
output:
? -100000000 -100000000 -100000000 100000000 ? -34227246 0 48996828 -83224075 48996827 83224075 ! 48996829 -83224075
result:
ok correct answer
Test #9:
score: 9
Accepted
time: 1ms
memory: 3872kb
input:
100000000 1 10000 120187009 222454927 2 102267915 102267918 102267919
output:
? -100000000 -100000000 -100000000 100000000 ? -79812991 0 -28679033 -51133959 -28679034 51133959 22454924 0 ! -28679032 51133959
result:
ok correct answer
Test #10:
score: 9
Accepted
time: 1ms
memory: 3756kb
input:
100000000 1 10000 200000000 400000000 2 200000000 200000001
output:
? -100000000 -100000000 -100000000 100000000 ? 0 0 99999999 -100000000 99999998 100000000 ! 100000000 100000000
result:
ok correct answer
Test #11:
score: 9
Accepted
time: 1ms
memory: 3812kb
input:
100000000 1 10000 200000000 400000000 1 200000000 200000002
output:
? -100000000 -100000000 -100000000 100000000 ? 0 0 99999999 -100000000 99999998 100000000 ! 100000000 -100000000
result:
ok correct answer
Test #12:
score: 9
Accepted
time: 1ms
memory: 3880kb
input:
100000000 1 10000 0 200000000 1 199999998 200000000
output:
? -100000000 -100000000 -100000000 100000000 ? -100000000 -100000000 -99999999 100000000 -2 0 ! -100000000 100000000
result:
ok correct answer
Test #13:
score: 9
Accepted
time: 1ms
memory: 3784kb
input:
100000000 1 10000 0 200000000 0 199999998 200000001
output:
? -100000000 -100000000 -100000000 100000000 ? -100000000 -100000000 -99999999 100000000 -2 0 ! -100000000 -100000000
result:
ok correct answer
Subtask #2:
score: 0
Wrong Answer
Dependency #1:
100%
Accepted
Test #14:
score: 19
Accepted
time: 1ms
memory: 3884kb
input:
10 1 10000 20 30 2 7 10 11
output:
? -10 -10 -10 10 ? 0 0 4 -5 3 5 7 0 ! 5 5
result:
ok correct answer
Test #15:
score: 19
Accepted
time: 0ms
memory: 3760kb
input:
10 1 10000 28 30 2 3 4 5
output:
? -10 -10 -10 10 ? 8 0 8 -1 5 1 5 0 ! 9 1
result:
ok correct answer
Test #16:
score: 19
Accepted
time: 1ms
memory: 3892kb
input:
10 1 10000 13 29 2 13 16 17
output:
? -10 -10 -10 10 ? -7 0 0 -8 -1 8 6 0 ! 1 8
result:
ok correct answer
Test #17:
score: 19
Accepted
time: 1ms
memory: 3860kb
input:
10 1 10000 20 20 0
output:
? -10 -10 -10 10 ? 0 0 ! 0 0
result:
ok correct answer
Test #18:
score: 19
Accepted
time: 0ms
memory: 3792kb
input:
10 1 10000 30 30 0
output:
? -10 -10 -10 10 ? 10 0 ! 10 0
result:
ok correct answer
Test #19:
score: 19
Accepted
time: 1ms
memory: 3756kb
input:
10 1 10000 10 30 2 17 20 21
output:
? -10 -10 -10 10 ? -10 0 -1 -10 -2 10 7 0 ! 0 10
result:
ok correct answer
Test #20:
score: 19
Accepted
time: 1ms
memory: 3812kb
input:
10 1 10000 20 40 2 20 21
output:
? -10 -10 -10 10 ? 0 0 9 -10 8 10 ! 10 10
result:
ok correct answer
Test #21:
score: 19
Accepted
time: 0ms
memory: 3872kb
input:
100000000 1 10000 165772754 332220904 1 166448150 166448152
output:
? -100000000 -100000000 -100000000 100000000 ? -34227246 0 48996828 -83224075 48996827 83224075 ! 48996829 -83224075
result:
ok correct answer
Test #22:
score: 19
Accepted
time: 1ms
memory: 3948kb
input:
100000000 1 10000 120187009 222454927 2 102267915 102267918 102267919
output:
? -100000000 -100000000 -100000000 100000000 ? -79812991 0 -28679033 -51133959 -28679034 51133959 22454924 0 ! -28679032 51133959
result:
ok correct answer
Test #23:
score: 19
Accepted
time: 1ms
memory: 3872kb
input:
100000000 1 10000 200000000 400000000 2 200000000 200000001
output:
? -100000000 -100000000 -100000000 100000000 ? 0 0 99999999 -100000000 99999998 100000000 ! 100000000 100000000
result:
ok correct answer
Test #24:
score: 19
Accepted
time: 1ms
memory: 3864kb
input:
100000000 1 10000 200000000 400000000 1 200000000 200000002
output:
? -100000000 -100000000 -100000000 100000000 ? 0 0 99999999 -100000000 99999998 100000000 ! 100000000 -100000000
result:
ok correct answer
Test #25:
score: 19
Accepted
time: 1ms
memory: 3816kb
input:
100000000 1 10000 0 200000000 1 199999998 200000000
output:
? -100000000 -100000000 -100000000 100000000 ? -100000000 -100000000 -99999999 100000000 -2 0 ! -100000000 100000000
result:
ok correct answer
Test #26:
score: 19
Accepted
time: 1ms
memory: 3788kb
input:
100000000 1 10000 0 200000000 0 199999998 200000001
output:
? -100000000 -100000000 -100000000 100000000 ? -100000000 -100000000 -99999999 100000000 -2 0 ! -100000000 -100000000
result:
ok correct answer
Test #27:
score: 19
Accepted
time: 1ms
memory: 3772kb
input:
100 3 500 42 135 221 229 242 313 5 12 14 16 18 22 34 39 43 52 57 58 58 59 61 62 63 65 67 68 68 71 71 79 81 83 93 95 97 98 99 103 105 106 107 107 107 110 110 110 113 113 114 115 116 117 119 120 121 126 127 132 135 136 139 144 145 150 151 151 154 155 158 161 161 164 168 174 179 180 181 183 186 188 188...
output:
? -100 -100 -100 100 ? -69 -89 -70 89 -67 -93 -68 0 -69 93 -63 -100 -65 100 -32 -43 -33 43 -30 -47 -31 47 -26 -53 -32 53 0 0 -2 -89 -3 89 -3 -4 -7 4 -4 0 -3 -10 -4 10 -2 -6 -3 6 3 0 20 -46 8 46 11 -42 8 42 13 -35 7 35 ! -58 -100 -18 -47 67 46
result:
ok correct answer
Test #28:
score: 19
Accepted
time: 0ms
memory: 3836kb
input:
100 4 500 159 175 211 224 232 248 329 348 5 7 7 9 11 19 38 39 44 52 52 53 56 58 62 65 69 70 74 76 77 79 82 83 85 86 87 89 91 91 92 94 96 98 100 100 101 104 106 108 109 113 119 123 123 125 127 127 129 131 132 133 134 135 136 137 138 140 141 144 145 147 147 151 156 157 157 162 165 166 168 168 170 171 ...
output:
? -100 -100 -100 100 ? -41 0 -34 -8 -35 8 -28 0 -19 -26 -20 26 -15 -32 -16 32 -15 -18 -16 18 -15 -36 -16 36 -13 -24 -20 24 -30 -44 -31 -28 -32 28 -83 44 -76 -36 -90 0 -92 36 -87 -6 -93 6 -98 -10 -99 10 -124 0 -121 -4 -125 4 -149 -18 -154 18 -165 0 -165 -12 -169 12 -171 -8 -183 8 -186 -85 -187 85 -18...
result:
ok correct answer
Test #29:
score: 19
Accepted
time: 1ms
memory: 3928kb
input:
100 5 500 39 57 147 169 185 226 247 261 319 322 5 9 16 19 23 25 26 36 37 39 40 46 47 48 52 53 55 60 67 67 68 70 71 73 75 76 80 81 82 82 83 85 85 86 87 90 90 94 95 96 98 101 101 107 108 110 110 110 112 113 115 118 118 119 121 121 125 125 128 129 130 133 133 134 135 136 138 138 140 144 144 147 148 148...
output:
? -100 -100 -100 100 ? -98 -45 -99 45 -98 -65 -99 65 -92 -73 -93 73 -93 -56 -94 56 -87 -64 -88 64 -81 -93 -82 93 -76 -84 -83 84 -78 0 -76 -95 -85 95 -82 -11 -93 11 -86 -19 -87 19 -91 0 -92 -8 -105 8 -101 0 -101 -39 -102 39 -98 -50 -105 -28 -111 28 -166 50 -225 -57 -226 57 -228 -20 -233 20 -231 -39 -...
result:
ok correct answer
Test #30:
score: 19
Accepted
time: 0ms
memory: 3912kb
input:
100 6 500 85 98 119 150 157 165 171 225 254 264 270 290 8 9 13 17 20 30 31 34 37 38 39 41 42 44 46 49 52 55 61 66 68 70 70 70 72 73 76 79 81 84 85 88 90 93 96 97 100 106 108 109 112 115 118 126 127 129 129 130 130 131 141 142 145 148 150 151 151 152 156 158 161 163 165 166 167 169 169 170 173 175 17...
output:
? -100 -100 -100 100 ? -98 -17 -99 17 -94 -10 -95 10 -87 -32 -88 32 -87 0 -86 -36 -87 36 -85 -26 -139 26 -170 -40 -171 40 -170 -29 -172 29 -188 -43 -199 43 -200 -33 -202 33 -208 -36 -282 -15 -293 15 -306 36 -306 -19 -312 19 -334 -23 -335 23 -348 -26 -364 26 -360 0 -366 -3 -390 3 -398 -70 -414 70 -41...
result:
ok correct answer
Test #31:
score: 0
Wrong Answer
time: 7ms
memory: 4276kb
input:
100 10 500 56 104 110 120 123 129 145 148 151 177 183 188 213 242 255 260 317 325 333 361 21 22 23 26 27 30 30 32 33 35 35 37 38 40 42 43 45 45 47 48 49 50 51 52 54 54 55 55 56 56 57 57 59 59 60 62 63 64 66 67 69 72 74 75 76 82 83 89 90 91 91 93 94 95 95 96 97 98 98 101 103 104 111 130 132 134 135 1...
output:
? -100 -100 -100 100 ? -100 -44 -101 44 -100 -46 -101 46 -105 -47 -106 47 -106 0 -104 -3 -105 3 -103 0 -102 -8 -103 8 -106 -9 -192 9 -210 -5 -294 5 -329 -60 -336 -12 -337 -6 -357 6 -373 12 -381 60 -423 -63 -433 -9 -438 9 -463 63 -479 0 -530 -1 -531 1 -568 -66 -604 66 -606 0 -606 -20 -607 -4 -613 4 -...
result:
wrong answer your answer is incorrect
Subtask #3:
score: 0
Skipped
Dependency #2:
0%
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Runtime Error
Test #116:
score: 0
Runtime Error
input:
100 20 3 64 75 90 91 93 99 113 132 136 152 158 162 166 174 177 179 188 189 190 197 197 200 202 205 214 225 226 227 229 229 242 254 261 268 270 277 283 314 327 335
output:
? -100 -100 -100 100
result:
Subtask #6:
score: 0
Skipped
Dependency #5:
0%
Subtask #7:
score: 0
Skipped
Dependency #1:
100%
Accepted
Dependency #2:
0%