QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#825107#9770. Middle Pointucup-team6225#WA 0ms3840kbC++143.9kb2024-12-21 17:23:032024-12-21 17:23:13

Judging History

This is the latest submission verdict.

  • [2024-12-21 17:23:13]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3840kb
  • [2024-12-21 17:23:03]
  • Submitted

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 == a || x == 0)    return {};
    int l = 0, r = a;   vector<pii> tmp;
    py.pb(l), py.pb(r);
    while(l < r) {
        int mid = (l + r) >> 1;
        // cerr << l << " " << r << " " << mid << "\n";
        if((l + r) & 1) return {{-1, -1}};
        tmp.pb({l, r}), py.pb(mid), pre[mid] = {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()) {
                add(p.back().fi, 0), add(p.back().se, 0);
                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()) {
                add(0, q.back().fi), add(0, q.back().se);  
                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()) {
                add(p.back().fi, q.back().fi), add(p.back().se, q.back().se);
                id[{(p.back().fi + p.back().se) / 2, (q.back().fi + q.back().se) / 2}] = 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();
        }
    }
    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;
    add(x, y);
    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;
}

详细

Test #1:

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

input:

2 2
1 1

output:

1
0 0 2 2

result:

ok correct!

Test #2:

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

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

input:

0 0
0 0

output:

0

result:

ok correct!

Test #4:

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

input:

2024 0
1012 0

output:

1
0 0 2024 0

result:

ok correct!

Test #5:

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

input:

2024 2024
2023 2023

output:

-1

result:

ok correct!

Test #6:

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

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

input:

2024 2026
2024 2026

output:

0

result:

ok correct!

Test #8:

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

input:

1000000000 1000000000
70 0

output:

-1

result:

ok correct!

Test #9:

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

input:

3 6
2 4

output:

-1

result:

ok correct!

Test #10:

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

input:

7 7
7 2

output:

-1

result:

ok correct!

Test #11:

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

input:

6 2
5 2

output:

-1

result:

ok correct!

Test #12:

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

input:

5 7
5 5

output:

-1

result:

ok correct!

Test #13:

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

input:

4 7
2 3

output:

-1

result:

ok correct!

Test #14:

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

input:

8 2
2 2

output:

2
0 0 8 0
0 0 4 0

result:

wrong answer target point have not been added into S