QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#825276#9770. Middle Pointucup-team6225#WA 1ms4112kbC++144.4kb2024-12-21 17:57:222024-12-21 17:57:24

Judging History

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

  • [2024-12-21 17:57:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:4112kb
  • [2024-12-21 17:57:22]
  • 提交

answer

#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
using namespace std;

using pii = pair<int, int>;
const int N = 1000010, M = 1010, SZ = (1 << 18) + 5;
static char buf[SZ], *bgn = buf, *til = buf;
char getc() {
    if(bgn == til)  bgn = buf, til = buf + fread(buf, 1, SZ, stdin);
    return bgn == til ? EOF : *bgn++;
}
template<typename T>
void read(T &x) {
    char ch = getc();  T fh = 0;   x = 0;
    while(ch < '0' || ch > '9')    fh |= (ch == '-'), ch = getc();
    while(ch >= '0' && ch <= '9')   x = x * 10 + ch - '0', ch = getc();
    x = fh ? -x : x;
}
template<typename Type, typename... argc>
void read(Type &x, argc &...args)   {read(x), read(args...);}
template<typename T>
void print(T x) {
    if(x < 0)  putchar('-'), x = -x;
    if(x / 10)  print(x / 10);
    putchar(x % 10 + '0');
}
int a, b, x, y;
vector<int> px, py, edge[M];
map<pii, int> id;
map<int, pii> pre;
vector<pii> ap, aq;
vector<pii> merge(int a, int x) {
    // cerr << a << " " << x << "\n";
    if(x == 0)  return {{0, 0}};
    if(x == a)  return {{a, a}};
    int l = 0, r = a;   vector<pii> tmp;
    while(l < r) {
        int mid = (l + r) >> 1;
        // cerr << l << " " << r << " " << mid << "\n";
        if((l + r) & 1) return {{-1, -1}};
        tmp.pb({l, r});
        if(x == mid)    return tmp;
        else if(x < mid)    r = mid;
        else    l = mid;        
    }
    return tmp;
}
int add(int x, int y) {
    if(id.find({x, y}) != id.end()) return 0;
    vector<pii> p = merge(a, x), q = merge(b, y);
    if((!p.empty() && p[0].fi < 0) || (!q.empty() && q[0].fi < 0))  return -1;
    // int sum = max(p.size(), q.size());
    // // printf("%d\n", sum);
    // reverse(p.begin(), p.end()), reverse(q.begin(), q.end());
    // for(int i = 1; i <= sum; ++i) {
    //     if(p.size() > q.size()) {
    //         if(id.find({(p.back().fi + p.back().se) / 2, 0}) == id.end()) {
    //             int op1 = add(p.back().fi, 0), op2 = add(p.back().se, 0);
    //             if(op1 < 0 || op2 < 0)  return -1;
    //             id[{(p.back().fi + p.back().se) / 2, 0}] = 1;
    //             ap.pb({p.back().fi, 0}), aq.pb({p.back().se, 0});
    //             // fprintf(stderr, "%d 0 %d 0\n", p.back().fi, p.back().se);
    //         }
    //         p.pop_back();
    //     }
    //     else if(p.size() < q.size()) {
    //         if(id.find({0, (q.back().fi + q.back().se) / 2}) == id.end()) {
    //             int op1 = add(0, q.back().fi), op2 = add(0, q.back().se);  
    //             if(op1 < 0 || op2 < 0)  return -1;
    //             id[{0, (q.back().fi + q.back().se) / 2}] = 1;
    //             ap.pb({0, q.back().fi}), aq.pb({0, q.back().se});
    //             // fprintf(stderr, "0 %d 0 %d\n", q.back().fi, q.back().se);
    //         }
    //         q.pop_back();
    //     }
    //     else {
    //         if(id.find({(p.back().fi + p.back().se) / 2, (q.back().fi + q.back().se) / 2}) == id.end()) {
    //             int op1 = add(p.back().fi, q.back().fi), op2 = add(p.back().se, q.back().se);
    //             id[{(p.back().fi + p.back().se) / 2, (q.back().fi + q.back().se) / 2}] = 1;
    //             if(op1 < 0 || op2 < 0)  return -1;
    //             ap.pb({p.back().fi, q.back().fi}), aq.pb({p.back().se, q.back().se});
    //             // fprintf(stderr, "%d %d %d %d\n", p.back().fi, q.back().fi, p.back().se, q.back().se);
    //         }
    //         p.pop_back(), q.pop_back();
    //     }
    // }
    add(p.back().fi, q.back().fi), add(p.back().se, q.back().se);
    ap.pb({p.back().fi, q.back().fi}), aq.pb({p.back().se, q.back().se});
    id[{x, y}] = 1;
    return 1;
}
int main() {
    #ifdef Kelly
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        freopen("err.txt", "w", stderr);
    #endif
    cin >> a >> b >> x >> y;
    vector<pii> p = merge(a, x);
    swap(px, py);
    vector<pii> q = merge(b, y);
    // cerr << p.size() << " " << q.size() << "\n";
    if((!p.empty() && p[0].fi < 0) || (!q.empty() && q[0].fi < 0))    {cout << "-1";  return 0;}
    id[{0, 0}] = id[{0, b}] = id[{a, 0}] = id[{a, b}] = 1;
    if(add(x, y) < 0)   {cout << -1;    return 0;}
    printf("%d\n", (int)ap.size());
    for(int i = 0; i < ap.size(); ++i)  printf("%d %d %d %d\n", ap[i].fi, ap[i].se, aq[i].fi, aq[i].se);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2 2
1 1

output:

1
0 0 2 2

result:

ok correct!

Test #2:

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

input:

8 8
5 0

output:

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

result:

ok correct!

Test #3:

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

input:

0 0
0 0

output:

0

result:

ok correct!

Test #4:

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

input:

2024 0
1012 0

output:

1
0 0 2024 0

result:

ok correct!

Test #5:

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

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

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

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

input:

2024 2026
2024 2026

output:

0

result:

ok correct!

Test #8:

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

input:

1000000000 1000000000
70 0

output:

-1

result:

ok correct!

Test #9:

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

input:

3 6
2 4

output:

-1

result:

ok correct!

Test #10:

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

input:

7 7
7 2

output:

-1

result:

ok correct!

Test #11:

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

input:

6 2
5 2

output:

-1

result:

ok correct!

Test #12:

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

input:

5 7
5 5

output:

-1

result:

ok correct!

Test #13:

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

input:

4 7
2 3

output:

-1

result:

ok correct!

Test #14:

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

input:

8 2
2 2

output:

2
0 2 8 2
0 2 4 2

result:

ok correct!

Test #15:

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

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

input:

6 3
6 1

output:

-1

result:

ok correct!

Test #18:

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

input:

4 2
2 1

output:

1
0 0 4 2

result:

ok correct!

Test #19:

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

input:

7 2
3 2

output:

-1

result:

ok correct!

Test #20:

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

input:

2 7
0 3

output:

-1

result:

ok correct!

Test #21:

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

input:

1 7
1 0

output:

0

result:

ok correct!

Test #22:

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

input:

5 1
0 0

output:

0

result:

ok correct!

Test #23:

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

input:

8 7
4 3

output:

-1

result:

ok correct!

Test #24:

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

input:

180057652 674822131
110693180 428023738

output:

-1

result:

ok correct!

Test #25:

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

input:

62347541 812142018
42922107 486416913

output:

-1

result:

ok correct!

Test #26:

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

input:

239604722 244429197
78993837 108804105

output:

-1

result:

ok correct!

Test #27:

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

input:

416861903 381749084
375027630 373683256

output:

-1

result:

ok correct!

Test #28:

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

input:

594119084 519068971
429116021 298715088

output:

-1

result:

ok correct!

Test #29:

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

input:

536870912 536870912
233225286 372408647

output:

179
0 0 536870912 0
0 0 268435456 0
134217728 0 268435456 0
201326592 0 268435456 0
201326592 0 234881024 0
218103808 0 234881024 0
0 536870912 536870912 536870912
0 536870912 268435456 536870912
134217728 536870912 268435456 536870912
201326592 536870912 268435456 536870912
226492416 0 234881024 53...

result:

wrong answer Jury has a better answer