QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#584289#8270. Mineral depositshansiyuan9 12ms4224kbC++142.0kb2024-09-23 11:23:062024-09-23 11:23:07

Judging History

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

  • [2024-09-23 11:23:07]
  • 评测
  • 测评结果:9
  • 用时:12ms
  • 内存:4224kb
  • [2024-09-23 11:23:06]
  • 提交

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=0;j<a.size();j++){
        pii v = a[j];
       // if(i<j && Dis(v,p)==dt) printf("%d %d %d %d %d %d %d\n",dt,u.X,u.Y,v.X,v.Y,p.X,p.Y);
        if(key.count(Dis(v,p)) || i<j&&Dis(v,p)==dt) return false;
    }
    //printf("%d %d\n",p.X,p.Y);
    key.insert(dt);
    for(int j=0;j<a.size();j++)
        s.insert(Dis(a[j],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(s.count(d) || (!chk(i,-d,0) && !chk(i,d,0) && !chk(i,0,-d) && !chk(i,0,d))) 
            d++;
        dis[i] = 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: 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 #2:

score: 9
Accepted
time: 0ms
memory: 3820kb

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: 0ms
memory: 3768kb

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: 3824kb

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: 0ms
memory: 3892kb

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: 3884kb

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: 0ms
memory: 3900kb

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: 0ms
memory: 3764kb

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: 0ms
memory: 3944kb

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: 3772kb

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: 0ms
memory: 3944kb

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: 3808kb

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: 3900kb

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
Runtime Error

Dependency #1:

100%
Accepted

Test #14:

score: 19
Accepted
time: 0ms
memory: 3896kb

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: 1ms
memory: 3844kb

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: 3800kb

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: 3944kb

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: 1ms
memory: 3888kb

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: 3892kb

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: 3904kb

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: 3824kb

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: 3952kb

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: 3952kb

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: 3828kb

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: 0ms
memory: 3884kb

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: 3892kb

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: 3860kb

input:

100 3 500
42 135 221 229 242 313
5 12 14 16 18 22 23 24 47 52 57 58 58 61 62 64 65 67 68 71 79 81 82 83 93 95 97 98 99 99 103 105 106 107 107 110 110 113 113 114 116 116 117 117 120 121 126 131 140 145 150 151 151 154 154 155 155 158 161 164 168 168 174 179 180 181 183 184 186 188 188 190 191 192 19...

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 -18 0 4 -46 67 110 1 -42 145 42 154 -35 155 35 
! -58 -100 -18 -47 67 46 

result:

ok correct answer

Test #28:

score: 19
Accepted
time: 1ms
memory: 3804kb

input:

100 4 500
159 175 211 224 232 248 329 348
5 7 9 11 21 38 39 39 44 45 52 52 53 56 58 62 65 71 74 76 77 79 82 83 85 86 86 89 91 92 94 96 97 100 106 107 108 109 109 113 119 123 123 124 127 127 128 131 134 134 135 137 139 141 142 144 144 145 145 151 152 153 156 157 157 162 166 167 170 171 171 174 174 17...

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 -1 -12 -34 24 -31 -44 -32 -28 -52 28 -82 44 -76 -36 -86 0 -91 36 -102 -6 -103 6 -103 -10 -108 10 -123 0 -136 -4 -169 4 -172 -18 -181 18 -184 0 -183 -12 -203 12 -209 -8 -232 8 -232 -85 -233 85 ...

result:

ok correct answer

Test #29:

score: 19
Accepted
time: 1ms
memory: 3940kb

input:

100 5 500
39 57 147 169 185 226 247 261 319 322
5 9 16 19 23 26 36 37 39 40 46 47 51 53 55 56 63 67 67 70 71 74 75 76 81 82 82 83 85 85 86 88 90 90 95 96 98 99 101 107 110 112 113 114 118 119 119 121 121 125 126 128 133 133 134 135 136 137 138 138 138 140 143 144 144 147 148 148 150 151 157 163 167 ...

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 -11 95 -82 -11 -83 11 -85 -19 -86 19 -86 0 -92 -8 -105 8 -101 0 -102 -39 -130 39 -166 -50 -182 -28 -186 28 -236 50 -234 -57 -239 57 -239 -20 -241 20 -240 -39 ...

result:

ok correct answer

Test #30:

score: 19
Accepted
time: 3ms
memory: 4016kb

input:

100 6 500
85 98 119 150 157 165 171 225 254 264 270 290
8 9 13 17 20 24 31 34 37 38 39 41 42 44 46 49 52 55 56 61 66 70 70 72 73 74 76 79 81 84 85 88 90 93 96 97 100 106 108 109 112 118 119 127 129 129 130 131 134 141 145 147 148 150 151 151 152 156 158 161 166 167 169 169 170 173 175 176 176 177 18...

output:

? -100 -100 -100 100
? -98 -17 -99 17 -94 -10 -95 10 -87 -32 -88 32 -87 0 -86 -36 -87 36 -76 -17 -143 26 -170 -40 -171 40 -170 -29 -172 29 -188 -43 -199 43 -200 -33 -285 33 -284 -36 -293 -15 -295 15 -307 36 -309 -19 -371 19 -377 -23 -384 23 -383 -26 -391 26 -425 0 -440 -3 -450 3 -481 -70 -482 70 -43...

result:

ok correct answer

Test #31:

score: 19
Accepted
time: 12ms
memory: 4224kb

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 -607 0 -607 -20 -652 -4 -681 4 -...

result:

ok correct answer

Test #32:

score: 0
Runtime Error

input:

100 20 500
45 68 69 76 77 109 122 131 138 147 149 153 159 172 177 177 183 185 195 204 205 209 210 212 243 245 249 267 270 281 283 285 287 291 298 306 326 331 337 357

output:

? -100 -100 -100 100

result:


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%