QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#826547#7917. KlompendansBrno (Bocheng Jiang, Zhenyu Wang, Taixiang Wang)#AC ✓26ms6532kbC++201.5kb2024-12-22 13:46:462024-12-22 13:46:48

Judging History

This is the latest submission verdict.

  • [2024-12-22 13:46:48]
  • Judged
  • Verdict: AC
  • Time: 26ms
  • Memory: 6532kb
  • [2024-12-22 13:46:46]
  • Submitted

answer

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define mk make_pair
#define MID int mid=(l+r)>>1;
#define ll long long
#define endl '\n'
#define siz(a) int(a.size())
int dis[510][510][2];
int a,b,c,d,n;
int fx1[]={0,0,1,-1,0,0,1,-1};
int fy1[]={1,-1,0,0,1,-1,0,0};
int fx2[]={1,-1,0,0,-1,1,0,0};
int fy2[]={0,0,1,-1,0,0,-1,1};
struct node{
    int x,y,tp;
};
queue<node>q;
bool ck(int x,int y){
    return x>=1&&y>=1&&x<=n&&y<=n;
}
void bfs(){
    memset(dis,-1,sizeof(dis));
    dis[1][1][0]=dis[1][1][1]=1;
    q.push(node{1,1,0});
    q.push(node{1,1,1});
    while(!q.empty()){
        node u=q.front();q.pop();
        for(int i=0;i<8;i++){
            node v;
            if(u.tp==1){
                v=node{u.x+fx1[i]*c+fx2[i]*d,u.y+fy1[i]*c+fy2[i]*d,0};
            }
            else{
                v=node{u.x+fx1[i]*a+fx2[i]*b,u.y+fy1[i]*a+fy2[i]*b,1};
            }
            if(!ck(v.x,v.y)||dis[v.x][v.y][v.tp]==1)continue;
            dis[v.x][v.y][v.tp]=1;
            q.push(v);
        }
    }
}
void solveclr(){

}
void solve(){
    solveclr();
    cin>>n>>a>>b>>c>>d;
    bfs();
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            if(dis[i][j][0]==1||dis[i][j][1]==1)ans++;
        }
    }
    cout<<ans;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT;
    // cin>>TTT;
    TTT=1;
    while(TTT--)solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5816kb

input:

3
2 1
2 2

output:

6

result:

ok single line: '6'

Test #2:

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

input:

8
1 2
1 2

output:

64

result:

ok single line: '64'

Test #3:

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

input:

4
1 2
2 3

output:

13

result:

ok single line: '13'

Test #4:

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

input:

5
1 2
2 3

output:

25

result:

ok single line: '25'

Test #5:

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

input:

10
3 3
4 4

output:

50

result:

ok single line: '50'

Test #6:

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

input:

3
1 1
1 1

output:

5

result:

ok single line: '5'

Test #7:

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

input:

500
499 499
499 499

output:

2

result:

ok single line: '2'

Test #8:

score: 0
Accepted
time: 13ms
memory: 5600kb

input:

500
1 1
1 2

output:

250000

result:

ok single line: '250000'

Test #9:

score: 0
Accepted
time: 12ms
memory: 5592kb

input:

500
250 250
250 249

output:

250000

result:

ok single line: '250000'

Test #10:

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

input:

293
52 290
100 225

output:

9

result:

ok single line: '9'

Test #11:

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

input:

81
1 67
38 10

output:

3057

result:

ok single line: '3057'

Test #12:

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

input:

49
44 9
11 45

output:

501

result:

ok single line: '501'

Test #13:

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

input:

313
220 140
166 196

output:

15467

result:

ok single line: '15467'

Test #14:

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

input:

490
268 481
286 10

output:

9

result:

ok single line: '9'

Test #15:

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

input:

411
156 396
38 119

output:

13

result:

ok single line: '13'

Test #16:

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

input:

19
11 16
6 15

output:

73

result:

ok single line: '73'

Test #17:

score: 0
Accepted
time: 2ms
memory: 5608kb

input:

472
29 175
273 321

output:

69211

result:

ok single line: '69211'

Test #18:

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

input:

271
228 10
242 201

output:

19004

result:

ok single line: '19004'

Test #19:

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

input:

78
75 77
35 6

output:

9

result:

ok single line: '9'

Test #20:

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

input:

71
69 65
3 9

output:

11

result:

ok single line: '11'

Test #21:

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

input:

100
98 40
9 1

output:

950

result:

ok single line: '950'

Test #22:

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

input:

87
10 7
3 86

output:

9

result:

ok single line: '9'

Test #23:

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

input:

84
83 78
10 75

output:

9

result:

ok single line: '9'

Test #24:

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

input:

85
81 75
3 75

output:

36

result:

ok single line: '36'

Test #25:

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

input:

71
53 67
70 63

output:

7

result:

ok single line: '7'

Test #26:

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

input:

51
25 41
1 2

output:

1872

result:

ok single line: '1872'

Test #27:

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

input:

62
4 61
54 60

output:

7

result:

ok single line: '7'

Test #28:

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

input:

88
78 80
80 5

output:

352

result:

ok single line: '352'

Test #29:

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

input:

76
16 9
9 3

output:

5776

result:

ok single line: '5776'

Test #30:

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

input:

76
71 72
70 33

output:

9

result:

ok single line: '9'

Test #31:

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

input:

75
27 36
72 7

output:

9

result:

ok single line: '9'

Test #32:

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

input:

47
2 3
29 38

output:

716

result:

ok single line: '716'

Test #33:

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

input:

42
13 2
36 38

output:

13

result:

ok single line: '13'

Test #34:

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

input:

70
69 52
4 69

output:

23

result:

ok single line: '23'

Test #35:

score: 0
Accepted
time: 2ms
memory: 5656kb

input:

91
12 6
47 1

output:

4141

result:

ok single line: '4141'

Test #36:

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

input:

74
2 72
4 35

output:

9

result:

ok single line: '9'

Test #37:

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

input:

53
13 43
22 5

output:

2665

result:

ok single line: '2665'

Test #38:

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

input:

258
252 146
89 251

output:

218

result:

ok single line: '218'

Test #39:

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

input:

315
5 103
311 305

output:

11

result:

ok single line: '11'

Test #40:

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

input:

266
263 3
3 2

output:

4904

result:

ok single line: '4904'

Test #41:

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

input:

412
409 326
408 1

output:

80

result:

ok single line: '80'

Test #42:

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

input:

383
354 276
373 376

output:

9

result:

ok single line: '9'

Test #43:

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

input:

279
276 5
9 277

output:

44

result:

ok single line: '44'

Test #44:

score: 0
Accepted
time: 6ms
memory: 6220kb

input:

309
8 71
7 38

output:

95481

result:

ok single line: '95481'

Test #45:

score: 0
Accepted
time: 7ms
memory: 5868kb

input:

290
5 4
6 112

output:

84100

result:

ok single line: '84100'

Test #46:

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

input:

168
167 79
163 82

output:

7

result:

ok single line: '7'

Test #47:

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

input:

70
1 61
1 22

output:

3876

result:

ok single line: '3876'

Test #48:

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

input:

494
4 491
10 4

output:

25

result:

ok single line: '25'

Test #49:

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

input:

494
486 6
7 490

output:

28

result:

ok single line: '28'

Test #50:

score: 0
Accepted
time: 2ms
memory: 5568kb

input:

490
370 8
480 9

output:

5754

result:

ok single line: '5754'

Test #51:

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

input:

490
97 2
139 489

output:

13

result:

ok single line: '13'

Test #52:

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

input:

493
136 5
484 10

output:

38576

result:

ok single line: '38576'

Test #53:

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

input:

492
490 483
486 10

output:

7

result:

ok single line: '7'

Test #54:

score: 0
Accepted
time: 26ms
memory: 6532kb

input:

490
85 4
305 29

output:

240100

result:

ok single line: '240100'

Test #55:

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

input:

493
77 405
7 488

output:

9

result:

ok single line: '9'

Test #56:

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

input:

494
195 10
1 7

output:

244036

result:

ok single line: '244036'

Test #57:

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

input:

494
12 486
353 3

output:

2306

result:

ok single line: '2306'

Test #58:

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

input:

492
488 483
10 2

output:

13

result:

ok single line: '13'

Test #59:

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

input:

495
30 7
10 178

output:

245025

result:

ok single line: '245025'

Test #60:

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

input:

500
9 494
496 481

output:

26

result:

ok single line: '26'

Test #61:

score: 0
Accepted
time: 2ms
memory: 5560kb

input:

495
6 487
487 10

output:

15584

result:

ok single line: '15584'

Test #62:

score: 0
Accepted
time: 3ms
memory: 5864kb

input:

490
5 476
374 2

output:

25584

result:

ok single line: '25584'

Test #63:

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

input:

493
391 49
484 254

output:

9

result:

ok single line: '9'

Test #64:

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

input:

493
5 491
485 490

output:

23

result:

ok single line: '23'

Test #65:

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

input:

499
12 8
494 10

output:

26

result:

ok single line: '26'

Test #66:

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

input:

499
496 23
6 493

output:

9

result:

ok single line: '9'

Test #67:

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

input:

49
2 10
21 45

output:

764

result:

ok single line: '764'

Test #68:

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

input:

43
6 1
39 30

output:

348

result:

ok single line: '348'

Test #69:

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

input:

46
10 37
19 8

output:

1366

result:

ok single line: '1366'

Test #70:

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

input:

44
34 13
9 17

output:

1792

result:

ok single line: '1792'

Test #71:

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

input:

43
32 35
4 30

output:

501

result:

ok single line: '501'

Test #72:

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

input:

50
7 47
1 9

output:

602

result:

ok single line: '602'

Test #73:

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

input:

41
17 10
31 10

output:

1264

result:

ok single line: '1264'

Test #74:

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

input:

49
11 41
35 6

output:

643

result:

ok single line: '643'

Test #75:

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

input:

48
36 3
33 2

output:

1364

result:

ok single line: '1364'

Test #76:

score: 0
Accepted
time: 3ms
memory: 5632kb

input:

220
192 115
24 44

output:

33064

result:

ok single line: '33064'

Test #77:

score: 0
Accepted
time: 4ms
memory: 5660kb

input:

312
168 177
235 92

output:

69173

result:

ok single line: '69173'

Test #78:

score: 0
Accepted
time: 6ms
memory: 5600kb

input:

428
342 203
90 289

output:

115825

result:

ok single line: '115825'

Test #79:

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

input:

287
122 185
144 161

output:

68220

result:

ok single line: '68220'

Test #80:

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

input:

51
12 1
47 31

output:

425

result:

ok single line: '425'

Test #81:

score: 0
Accepted
time: 2ms
memory: 5556kb

input:

218
122 2
171 73

output:

6191

result:

ok single line: '6191'

Test #82:

score: 0
Accepted
time: 2ms
memory: 5628kb

input:

293
134 223
59 85

output:

5092

result:

ok single line: '5092'

Test #83:

score: 0
Accepted
time: 2ms
memory: 5624kb

input:

148
94 41
33 114

output:

12991

result:

ok single line: '12991'