QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#863021 | #9770. Middle Point | MonkeyKing | TL | 0ms | 0kb | C++14 | 3.9kb | 2025-01-19 11:45:58 | 2025-01-19 11:46:03 |
answer
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
int main() {
ll A, B, X, Y;
cin >> A >> B;
cin >> X >> Y;
vector<pair<pll, pll>> operations;
// Function to generate sequence of operations for coordinate
auto generate_operations = [](ll coord_max, ll target_coord) -> vector<pll> {
vector<pll> ops;
if (coord_max % 2 != 0) {
// Only 0 and coord_max are possible
if (target_coord != 0 && target_coord != coord_max) {
ops.push_back({-1, -1});
return ops;
} else {
return ops;
}
} else {
ll L = 0, R = coord_max;
while (L != target_coord) {
ll M = (L + R) / 2;
ops.push_back({L, R});
if (target_coord <= M) {
R = M;
} else {
L = M;
}
}
return ops;
}
};
vector<pll> x_ops, y_ops;
if (A % 2 == 1) {
if (X != 0 && X != A) {
cout << -1 << endl;
return 0;
}
} else {
x_ops = generate_operations(A, X);
if (!x_ops.empty() && x_ops[0].first == -1) {
cout << -1 << endl;
return 0;
}
}
if (B % 2 == 1) {
if (Y != 0 && Y != B) {
cout << -1 << endl;
return 0;
}
} else {
y_ops = generate_operations(B, Y);
if (!y_ops.empty() && y_ops[0].first == -1) {
cout << -1 << endl;
return 0;
}
}
vector<pll> points; // List of points currently in S
set<pll> point_set;
if (A != 0 && B != 0) {
points.push_back({0, 0});
points.push_back({0, B});
points.push_back({A, 0});
points.push_back({A, B});
} else if (A == 0 && B != 0) {
points.push_back({0, 0});
points.push_back({0, B});
} else if (A != 0 && B == 0) {
points.push_back({0, 0});
points.push_back({A, 0});
} else {
points.push_back({0, 0});
}
for (auto p : points) {
point_set.insert(p);
}
vector<pair<pll, pll>> total_ops;
// Map to find points with particular x or y
map<ll, pll> x_to_point, y_to_point;
for (auto p : points) {
x_to_point[p.first] = p;
y_to_point[p.second] = p;
}
// Process x operations
for (auto op : x_ops) {
ll Lx = op.first, Rx = op.second;
pll P = x_to_point[Lx];
pll Q = x_to_point[Rx];
// For y, take any existing y-coordinate (we can choose any since it's arbitrary)
pll new_point = {(Lx + Rx) / 2, P.second};
total_ops.push_back({P, Q});
x_to_point[(Lx + Rx) / 2] = new_point;
if (point_set.find(new_point) == point_set.end()) {
points.push_back(new_point);
point_set.insert(new_point);
}
}
// Process y operations
for (auto op : y_ops) {
ll Ly = op.first, Ry = op.second;
pll P = y_to_point[Ly];
pll Q = y_to_point[Ry];
// For x, take any existing x-coordinate (we can choose any since it's arbitrary)
pll new_point = {P.first, (Ly + Ry) / 2};
total_ops.push_back({P, Q});
y_to_point[(Ly + Ry) / 2] = new_point;
if (point_set.find(new_point) == point_set.end()) {
points.push_back(new_point);
point_set.insert(new_point);
}
}
cout << total_ops.size() << endl;
for (auto op : total_ops) {
cout << op.first.first << " " << op.first.second << " "
<< op.second.first << " " << op.second.second << endl;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
2 2 1 1