QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#583399 | #9172. Alternating Cycle | ucup-team4435# | WA | 1ms | 5764kb | C++20 | 5.6kb | 2024-09-22 19:49:16 | 2024-09-22 19:49:17 |
Judging History
answer
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;
int Bit(int mask, int b) { return (mask >> b) & 1; }
template<class T>
bool ckmin(T &a, const T &b) {
if (b < a) {
a = b;
return true;
}
return false;
}
template<class T>
bool ckmax(T &a, const T &b) {
if (b > a) {
a = b;
return true;
}
return false;
}
// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
--l;
while (r - l > 1) {
T mid = l + (r - l) / 2;
if (predicat(mid)) {
r = mid;
} else {
l = mid;
}
}
return r;
}
template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
return FindFirstTrue(l, r, predicat) - 1;
}
const ll INF = 2e18;
const int INFi = 1e9;
const int N = 3e5 + 5;
const int LG = 20;
struct Point {
int x, y;
Point(int x_ = 0, int y_ = 0) : x(x_), y(y_) {}
Point operator-(const Point &oth) const {
return {x - oth.x, y - oth.y};
}
ll operator*(const Point &oth) const {
return 1ll * x * oth.y - 1ll * y * oth.x;
}
ll length() const {
return 1ll * x * x + 1ll * y * y;
}
};
using pt = Point;
vector<pt> A;
int ang_type(int a, int b, int c) {
ll v = (A[b] - A[a]) * (A[c] - A[b]);
if (v > 0) return 1;
if (v < 0) return 2;
return 0;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int SZ = 500;
char tp[SZ][SZ][SZ];
pair<vector<Point>, vector<Point>> convex_hull(vector<Point> a) {
int n = a.size();
for (int i = 1; i < n; i++) {
if (make_pair(a[i].x, a[i].y) < make_pair(a[0].x, a[0].y)) {
swap(a[i], a[0]);
}
}
sort(1 + all(a), [&](Point p, Point q) {
p = p - a[0];
q = q - a[0];
ll prod = p * q;
if (prod != 0) {
return prod > 0;
}
return p.length() < q.length();
});
vector<Point> hull = {a[0], a[1]}, rem;
for (int i = 2; i < n; i++) {
while ((hull.back() - hull[int(hull.size()) - 2]) * (a[i] - hull.back()) < 0) {
rem.push_back(hull.back());
hull.pop_back();
}
hull.push_back(a[i]);
}
return {hull, rem};
}
void solve() {
int n;
cin >> n;
A.resize(n);
rep(i, n) cin >> A[i].x >> A[i].y;
vector<vector<pt>> keks;
while (keks.size() < 5 && !A.empty()) {
auto [lol, kek] = convex_hull(A);
keks.push_back(lol);
A = kek;
}
if (!A.empty()) {
keks.push_back(A);
}
A.clear();
rep(j, keks.size()) {
shuffle(all(keks[j]), rng);
}
rep(i, n) {
rep(j, keks.size()) {
if (keks[j].empty()) continue;
A.push_back(keks[j].back());
keks[j].pop_back();
}
}
for (int s0 = 0; s0 < n; ++s0) {
if (clock() / (1.0 * CLOCKS_PER_SEC) >= 1.8) {
break;
}
for(int i = 0; i < s0; ++i) {
for(int j = 0; j < s0; ++j) {
if (i == j) continue;
tp[i][j][s0] = ang_type(i, j, s0);
tp[i][s0][j] = ang_type(i, s0, j);
tp[s0][i][j] = ang_type(s0, i, j);
}
}
rep(s1, s0) {
rep(s2, s0) {
if (s2 == s1) continue;
rep(s3, s0) {
if (s3 == s1 || s3 == s2 || tp[s0][s1][s2] == tp[s1][s2][s3]) continue;
rep(s4, s0) {
if (s4 == s3 || s4 == s2 || s4 == s1 || tp[s1][s2][s3] == tp[s2][s3][s4]) continue;
rep(s5, s1) {
if (s1 == s5 || s2 == s5 || s5 == s3 || s5 == s4 || tp[s2][s3][s4] == tp[s3][s4][s5] || tp[s3][s4][s5] == tp[s4][s5][s0] || tp[s4][s5][s0] == tp[s5][s0][s1] || tp[s5][s0][s1] == tp[s0][s1][s2]) continue;
cout << "6\n";
cout << A[s0].x << ' ' << A[s0].y << '\n';
cout << A[s1].x << ' ' << A[s1].y << '\n';
cout << A[s2].x << ' ' << A[s2].y << '\n';
cout << A[s3].x << ' ' << A[s3].y << '\n';
cout << A[s4].x << ' ' << A[s4].y << '\n';
cout << A[s5].x << ' ' << A[s5].y << '\n';
return;
}
}
}
}
}
}
cout << "-1\n";
}
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout << setprecision(12) << fixed;
int t = 1;
// cin >> t;
rep(i, t) {
solve();
}
// cout << sizeof(a) / 1'000'000 << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5752kb
input:
6 10 15 20 15 15 23 0 31 15 0 30 30
output:
6 20 15 15 0 10 15 0 31 15 23 30 30
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3872kb
input:
4 0 0 0 1 1 0 1 1
output:
-1
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 3716kb
input:
9 693150551 810053304 26684055 999173154 767007508 725151476 697948407 601311897 593914132 156628727 294286621 249587903 361249906 42266067 110658137 698550461 923704821 886066345
output:
6 361249906 42266067 697948407 601311897 923704821 886066345 693150551 810053304 26684055 999173154 294286621 249587903
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
9 870407732 947373192 362190573 311657719 792350850 916217578 908809410 529664178 147184624 105531482 800863654 27569449 290489622 819212758 64484618 355712627 474856219 425123887
output:
6 792350850 916217578 870407732 947373192 362190573 311657719 474856219 425123887 800863654 27569449 290489622 819212758
result:
ok Everything ok
Test #5:
score: -100
Wrong Answer
time: 1ms
memory: 5764kb
input:
9 47664912 379660370 66293309 34207701 186290410 443720168 456106901 458016459 995422410 349401528 602407977 731922069 588325559 932595937 608245683 644278574 657411398 627744942
output:
6 47664912 379660370 186290410 443720168 602407977 731922069 0 0 66293309 34207701 995422410 349401528
result:
wrong answer Points do not come from the original point set, or are not unique