QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#770236#9770. Middle PointPlentyOfPenalty#WA 0ms3680kbC++202.3kb2024-11-21 21:13:012024-11-21 21:13:01

Judging History

This is the latest submission verdict.

  • [2024-11-21 21:13:01]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3680kb
  • [2024-11-21 21:13:01]
  • Submitted

answer

#include <bits/stdc++.h>
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#ifdef memset0
#define log(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl '\n'
#define log(...) (void(0))
#endif
using namespace std;
using ll = long long;
using lf = long double;
using ull = unsigned long long;
using lll = __int128;

set<pair<int, int>> s;
vector<pair<int, int>> vec;

int a, b, a1, b1, a2, b2;

pair<int, int> get_lu(int x, int m) {
  if (x == 0) return make_pair(0, 0);
  if (x == m) return make_pair(m, m);
  int y = x & -x;
  return make_pair(x - y, x + y);
}

void search(int x, int y) {
  if (s.count(make_pair(x, y))) {
    return;
  }
  log("> search %d %d\n", x, y);
  s.insert(make_pair(x, y));
  auto [x1, x2] = get_lu(x, a2);
  auto [y1, y2] = get_lu(y, b2);
  log("! %d %d %d %d\n", x1, y1, x2, y2);
  if (x1 == 0 && y2 == b2) {
    swap(y1, y2);
  }
  search(x1, y1);
  search(x2, y2);
  vec.emplace_back(x, y);
}

vector<tuple<int, int, int, int>> ans;
void solve(int n, int m, int x, int y, int rx, int ry) {
  log("solve n=%d m=%d x=%d y=%d rx=%d ry=%d\n", n, m, x, y, rx, ry);
  if (x > 0 && x < n && x % 2 == 0) return solve(n / 2, m, x / 2, y, rx * 2, ry);
  if (y > 0 && y < m && y % 2 == 0) return solve(n, m / 2, x, y / 2, rx, ry * 2);
  if ((x == 0 || x == n) && (y == 0 || y == m)) {
    return;
  }

  int cx = x < n / 2 ? 0 : n;
  int cy = y < m / 2 ? 0 : m;
  int vx = x * 2 - cx;
  int vy = y * 2 - cy;
  solve(n, m, vx, vy, rx, ry);
  log(">> now=(%d, %d) v=(%d, %d) c=(%d, %d)\n", x, y, vx, vy, cx, cy);
  ans.emplace_back(vx * rx, vy * ry, cx * rx, cy * ry);
}

int main() {
#ifdef memset0
  freopen("C.in", "r", stdin);
#endif
  cin.tie(0)->sync_with_stdio(0);

  cin >> a >> b;
  if (a) {
    a1 = a, a2 = 1;
    while (a1 % 2 == 0) a1 >>= 1, a2 <<= 1;
  } else {
    a1 = 1, a2 = 0;
  }
  if (b) {
    b1 = b, b2 = 1;
    while (b1 % 2 == 0) b1 >>= 1, b2 <<= 1;
  } else {
    b1 = 1, b2 = 0;
  }
  log(">> %d %d %d %d\n", a1, b1, a2, b2);
  int x, y;
  cin >> x >> y;
  if (x % a1 || y % b1) {
    cout << -1 << endl;
    return 0;
  }
  x /= a1;
  y /= b1;
  solve(a2, b2, x, y, a1, b1);
  cout << sz(ans) << endl;
  for (auto [x1, y1, x2, y2] : ans) {
    cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
1 1

output:

1
0 0 2 2

result:

ok correct!

Test #2:

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

input:

8 8
5 0

output:

3
0 0 8 0
4 0 0 0
2 0 8 0

result:

ok correct!

Test #3:

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

input:

0 0
0 0

output:

0

result:

ok correct!

Test #4:

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

input:

2024 0
1012 0

output:

1
0 0 2024 0

result:

ok correct!

Test #5:

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

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

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

input:

8 6
7 3

output:

3
0 0 8 0
4 0 8 0
6 0 8 6

result:

ok correct!

Test #7:

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

input:

2024 2026
2024 2026

output:

0

result:

ok correct!

Test #8:

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

input:

1000000000 1000000000
70 0

output:

-1

result:

ok correct!

Test #9:

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

input:

3 6
2 4

output:

-1

result:

ok correct!

Test #10:

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

input:

7 7
7 2

output:

-1

result:

ok correct!

Test #11:

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

input:

6 2
5 2

output:

-1

result:

ok correct!

Test #12:

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

input:

5 7
5 5

output:

-1

result:

ok correct!

Test #13:

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

input:

4 7
2 3

output:

-1

result:

ok correct!

Test #14:

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

input:

8 2
2 2

output:

2
0 2 8 2
4 2 0 2

result:

ok correct!

Test #15:

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

input:

3 3
0 2

output:

-1

result:

ok correct!

Test #16:

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

input:

7 7
1 4

output:

-1

result:

ok correct!

Test #17:

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

input:

6 3
6 1

output:

-1

result:

ok correct!

Test #18:

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

input:

4 2
2 1

output:

1
0 0 4 2

result:

ok correct!

Test #19:

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

input:

7 2
3 2

output:

-1

result:

ok correct!

Test #20:

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

input:

2 7
0 3

output:

-1

result:

ok correct!

Test #21:

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

input:

1 7
1 0

output:

0

result:

ok correct!

Test #22:

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

input:

5 1
0 0

output:

0

result:

ok correct!

Test #23:

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

input:

8 7
4 3

output:

-1

result:

ok correct!

Test #24:

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

input:

180057652 674822131
110693180 428023738

output:

-1

result:

ok correct!

Test #25:

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

input:

62347541 812142018
42922107 486416913

output:

-1

result:

ok correct!

Test #26:

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

input:

239604722 244429197
78993837 108804105

output:

-1

result:

ok correct!

Test #27:

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

input:

416861903 381749084
375027630 373683256

output:

-1

result:

ok correct!

Test #28:

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

input:

594119084 519068971
429116021 298715088

output:

-1

result:

ok correct!

Test #29:

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

input:

536870912 536870912
233225286 372408647

output:

29
0 0 0 536870912
0 268435456 536870912 536870912
268435456 402653184 536870912 536870912
402653184 469762048 0 0
201326592 234881024 0 0
100663296 117440512 0 0
50331648 58720256 536870912 536870912
293601280 297795584 0 0
146800640 148897792 0 536870912
73400320 342884352 0 0
36700160 171442176 5...

result:

ok correct!

Test #30:

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

input:

536870912 536870912
242171716 210314503

output:

29
0 0 0 536870912
0 268435456 0 536870912
0 402653184 536870912 536870912
268435456 469762048 0 0
134217728 234881024 0 0
67108864 117440512 0 0
33554432 58720256 536870912 0
285212672 29360128 0 0
142606336 14680064 536870912 536870912
339738624 275775488 536870912 0
438304768 137887744 536870912 ...

result:

ok correct!

Test #31:

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

input:

536870912 536870912
251118145 48220392

output:

29
0 0 536870912 0
268435456 0 0 0
134217728 0 0 0
67108864 0 0 536870912
33554432 268435456 0 0
16777216 134217728 0 536870912
8388608 335544320 536870912 536870912
272629760 436207616 0 536870912
136314880 486539264 0 0
68157440 243269632 536870912 0
302514176 121634816 0 0
151257088 60817408 0 53...

result:

ok correct!

Test #32:

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

input:

126070784 536870912
70206899 483718753

output:

29
0 0 0 536870912
0 268435456 0 0
0 134217728 0 0
0 67108864 0 0
0 33554432 0 0
0 16777216 0 536870912
0 276824064 0 536870912
0 406847488 0 0
0 203423744 0 0
0 101711872 0 536870912
0 319291392 0 536870912
0 428081152 0 0
0 214040576 0 536870912
0 375455744 0 536870912
0 456163328 0 536870912
0 49...

result:

ok correct!

Test #33:

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

input:

134541312 536870912
92168682 321624642

output:

28
0 0 0 536870912
0 268435456 0 0
0 134217728 0 0
0 67108864 0 0
0 33554432 0 0
0 16777216 0 536870912
0 276824064 0 0
0 138412032 0 0
0 69206016 0 536870912
0 303038464 0 0
0 151519232 0 536870912
0 344195072 0 536870912
0 440532992 0 0
0 220266496 0 0
0 110133248 0 536870912
0 323502080 0 5368709...

result:

ok correct!

Test #34:

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

input:

605171712 536870912
492293004 159530531

output:

29
0 0 0 536870912
0 268435456 0 536870912
0 402653184 0 0
0 201326592 0 0
0 100663296 0 0
0 50331648 0 536870912
0 293601280 0 0
0 146800640 0 0
0 73400320 0 0
0 36700160 0 536870912
0 286785536 0 536870912
0 411828224 0 536870912
0 474349568 0 536870912
0 505610240 0 536870912
0 521240576 0 0
0 26...

result:

ok correct!

Test #35:

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

input:

816447488 872415232
107288296 282864296

output:

23
0 0 0 872415232
0 436207616 0 0
0 218103808 0 0
0 109051904 0 872415232
0 490733568 0 0
0 245366784 0 872415232
0 558891008 0 872415232
0 715653120 0 0
0 357826560 0 0
0 178913280 816447488 0
408223744 89456640 0 0
204111872 44728320 0 0
102055936 22364160 816447488 0
459251712 11182080 0 0
22962...

result:

ok correct!

Test #36:

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

input:

465043456 805306368
155625924 290419248

output:

24
0 0 0 805306368
0 402653184 0 0
0 201326592 0 0
0 100663296 0 0
0 50331648 0 0
0 25165824 0 805306368
0 415236096 0 805306368
0 610271232 465043456 0
232521728 305135616 465043456 0
348782592 152567808 465043456 805306368
406913024 478937088 0 0
203456512 239468544 465043456 0
334249984 119734272...

result:

ok correct!

Test #37:

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

input:

246022144 587202560
78513033 233147565

output:

24
0 0 0 587202560
0 293601280 0 587202560
0 440401920 0 587202560
0 513802240 0 587202560
0 550502400 0 0
0 275251200 0 587202560
0 431226880 0 587202560
0 509214720 246022144 587202560
123011072 548208640 0 0
61505536 274104320 246022144 0
153763840 137052160 0 587202560
76881920 362127360 0 0
384...

result:

ok correct!

Test #38:

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

input:

536870912 699163134
414335415 699163134

output:

29
0 699163134 536870912 699163134
268435456 699163134 536870912 699163134
402653184 699163134 536870912 699163134
469762048 699163134 0 699163134
234881024 699163134 536870912 699163134
385875968 699163134 536870912 699163134
461373440 699163134 0 699163134
230686720 699163134 536870912 699163134
3...

result:

ok correct!

Test #39:

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

input:

536870912 292943687
423281845 292943687

output:

29
0 292943687 536870912 292943687
268435456 292943687 0 292943687
134217728 292943687 536870912 292943687
335544320 292943687 0 292943687
167772160 292943687 536870912 292943687
352321536 292943687 536870912 292943687
444596224 292943687 0 292943687
222298112 292943687 536870912 292943687
379584512...

result:

ok correct!

Test #40:

score: -100
Wrong Answer
time: 0ms
memory: 3608kb

input:

536870912 31948433
432228266 0

output:

33
0 0 0 0
0 -2147483648 0 0
0 -1073741824 0 0
0 -536870912 0 0
0 -268435456 0 0
0 2013265920 536870912 0
268435456 -1140850688 0 0
134217728 -570425344 536870912 0
335544320 1862270976 0 0
167772160 -1216348160 536870912 0
352321536 1539309568 0 0
176160768 769654784 536870912 0
356515840 384827392...

result:

wrong answer Integer -2147483648 violates the range [0, 10^9]