QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#583404 | #9172. Alternating Cycle | ucup-team4435# | WA | 1ms | 5956kb | C++20 | 5.5kb | 2024-09-22 19:50:22 | 2024-09-22 19:50:22 |
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) {
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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
6 10 15 20 15 15 23 0 31 15 0 30 30
output:
6 20 15 30 30 15 23 0 31 10 15 15 0
result:
ok Everything ok
Test #2:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
4 0 0 0 1 1 0 1 1
output:
-1
result:
ok Everything ok
Test #3:
score: 0
Accepted
time: 0ms
memory: 5796kb
input:
9 693150551 810053304 26684055 999173154 767007508 725151476 697948407 601311897 593914132 156628727 294286621 249587903 361249906 42266067 110658137 698550461 923704821 886066345
output:
6 767007508 725151476 697948407 601311897 593914132 156628727 110658137 698550461 294286621 249587903 361249906 42266067
result:
ok Everything ok
Test #4:
score: 0
Accepted
time: 1ms
memory: 5876kb
input:
9 870407732 947373192 362190573 311657719 792350850 916217578 908809410 529664178 147184624 105531482 800863654 27569449 290489622 819212758 64484618 355712627 474856219 425123887
output:
6 870407732 947373192 362190573 311657719 474856219 425123887 908809410 529664178 290489622 819212758 792350850 916217578
result:
ok Everything ok
Test #5:
score: 0
Accepted
time: 1ms
memory: 5672kb
input:
9 47664912 379660370 66293309 34207701 186290410 443720168 456106901 458016459 995422410 349401528 602407977 731922069 588325559 932595937 608245683 644278574 657411398 627744942
output:
6 588325559 932595937 608245683 644278574 995422410 349401528 456106901 458016459 47664912 379660370 186290410 443720168
result:
ok Everything ok
Test #6:
score: 0
Accepted
time: 1ms
memory: 5596kb
input:
9 224922093 516980257 696767119 51724974 580229972 266190050 593338977 91401448 843660194 888238866 108985009 509903616 591194203 709542627 225635675 932844521 618628214 461769776
output:
6 618628214 461769776 843660194 888238866 591194203 709542627 224922093 516980257 580229972 266190050 593338977 91401448
result:
ok Everything ok
Test #7:
score: 0
Accepted
time: 0ms
memory: 3900kb
input:
9 107211982 359332853 695837148 142871176 605573313 162288860 509232688 314721021 396930687 132108911 205496625 287885162 183997430 822925807 474429448 221410467 801183393 664390830
output:
6 695837148 142871176 509232688 314721021 183997430 822925807 605573313 162288860 474429448 221410467 107211982 359332853
result:
ok Everything ok
Test #8:
score: 0
Accepted
time: 0ms
memory: 3600kb
input:
9 284469163 791620032 31343664 160388450 294480166 689791450 351497471 948106011 245168471 81011666 7040948 65866709 481833366 304905205 91819440 215009122 983738573 203448372
output:
6 294480166 689791450 351497471 948106011 91819440 215009122 7040948 65866709 481833366 304905205 983738573 203448372
result:
ok Everything ok
Test #9:
score: 0
Accepted
time: 0ms
memory: 5756kb
input:
9 461726344 560343699 661817474 882938432 319823507 217294040 562358475 876458292 93406256 619849004 513617981 138815548 484702011 418288384 340613213 503575069 534889971 406069427
output:
6 562358475 876458292 461726344 560343699 319823507 217294040 661817474 882938432 534889971 406069427 513617981 138815548
result:
ok Everything ok
Test #10:
score: 0
Accepted
time: 0ms
memory: 5692kb
input:
9 638983525 992630879 660887503 900455706 713763069 113392850 404623258 99777864 646676749 863719050 315162304 548200875 782537947 195235074 958003206 160737235 422477859 945126970
output:
6 958003206 160737235 782537947 195235074 404623258 99777864 660887503 900455706 646676749 863719050 315162304 548200875
result:
ok Everything ok
Test #11:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
9 521273414 129950765 291361311 623005687 107702630 935862733 320516969 733162854 494914533 812621805 453143117 621149714 711777663 308618254 206796978 449303183 678661966 147748023
output:
6 494914533 812621805 453143117 621149714 521273414 129950765 291361311 623005687 107702630 935862733 320516969 733162854
result:
ok Everything ok
Test #12:
score: 0
Accepted
time: 1ms
memory: 5756kb
input:
8 563402439 725563321 430451262 152240853 780848346 860389268 888894820 499849356 415818421 408692535 840472921 429397462 326582722 561795426 53848834 517062841
output:
6 780848346 860389268 563402439 725563321 53848834 517062841 326582722 561795426 430451262 152240853 415818421 408692535
result:
ok Everything ok
Test #13:
score: 0
Accepted
time: 1ms
memory: 5784kb
input:
8 740659620 157850500 839586707 169758127 469755198 387891858 436192311 428201637 264056205 652562581 936984536 838782790 624418658 970145897 966206119 805628788
output:
-1
result:
ok Everything ok
Test #14:
score: 0
Accepted
time: 1ms
memory: 5872kb
input:
8 917916801 295170387 470060516 892308109 495098540 283990668 647053314 356553918 817326699 191399918 443561568 911731629 922254594 157158003 920032600 94194734
output:
-1
result:
ok Everything ok
Test #15:
score: 0
Accepted
time: 0ms
memory: 3668kb
input:
8 800206690 432490275 469130545 909825383 889038101 106460550 489318097 284906199 665564483 140302673 245105891 689713175 925123238 565508474 832389884 456389610
output:
-1
result:
ok Everything ok
Test #16:
score: 0
Accepted
time: 1ms
memory: 5692kb
input:
8 272431162 201213942 99604353 632375365 914381443 338995849 700179101 213258480 218834975 384172719 751682924 762662014 222959174 47487873 786216365 744955557
output:
-1
result:
ok Everything ok
Test #17:
score: 0
Accepted
time: 1ms
memory: 5732kb
input:
8 154721052 338533829 803707091 18488857 308321004 530061950 542443884 141610761 772105469 628042765 553227248 540643561 447166182 455838344 698573649 33521503
output:
6 698573649 33521503 542443884 141610761 154721052 338533829 772105469 628042765 553227248 540643561 308321004 530061950
result:
ok Everything ok
Test #18:
score: 0
Accepted
time: 1ms
memory: 5956kb
input:
8 331978233 475853717 434180900 741038840 997227857 57564540 384708667 774995751 620343253 871912811 354771571 950028888 450034826 937817743 947367422 322087450
output:
-1
result:
ok Everything ok
Test #19:
score: 0
Accepted
time: 1ms
memory: 5724kb
input:
8 214268122 908140896 64654708 758556113 727603907 585067131 595569671 998315324 468581038 115782857 861348604 728010435 747870762 346168213 196161194 610653397
output:
-1
result:
ok Everything ok
Test #20:
score: 0
Accepted
time: 1ms
memory: 5848kb
input:
8 686492595 45460782 63724737 776073387 121543467 776133233 142867162 926667605 21851530 359652903 589263999 800959274 45706698 828147612 108518478 267815563
output:
6 45706698 828147612 686492595 45460782 121543467 776133233 142867162 926667605 21851530 359652903 63724737 776073387
result:
ok Everything ok
Test #21:
score: 0
Accepted
time: 1ms
memory: 5740kb
input:
7 728621620 936040631 202814687 10341261 89656474 700659768 79841231 324757887 942755419 324319853 681626511 240610802 660511757 417761272
output:
-1
result:
ok Everything ok
Test #22:
score: 0
Accepted
time: 0ms
memory: 3724kb
input:
7 610911509 704764298 243353913 27858534 778563328 228162358 627138724 958142877 790993203 273222607 483170835 313559641 589751473 194707963
output:
6 483170835 313559641 243353913 27858534 589751473 194707963 778563328 228162358 610911509 704764298 627138724 958142877
result:
ok Everything ok
Test #23:
score: 0
Accepted
time: 1ms
memory: 5684kb
input:
7 493201398 842084186 242423942 750408517 172502889 755664949 132967018 550058669 639230987 812059946 284715158 91541188 887587409 308091142
output:
-1
result:
ok Everything ok
Test #24:
score: 0
Accepted
time: 1ms
memory: 5688kb
input:
7 965425871 274371364 872897751 767925791 197846230 651763759 680264510 183443658 192501480 55929991 791292191 164490026 890456054 85037832
output:
-1
result:
ok Everything ok
Test #25:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
7 847715760 116723959 871967780 490475772 591785792 179266348 522529294 111795939 40739264 4832745 592836514 647504282 188291989 198421011
output:
-1
result:
ok Everything ok
Test #26:
score: -100
Wrong Answer
time: 0ms
memory: 5744kb
input:
7 24972940 254043847 207474297 171556557 617129133 1736230 733390297 40148220 888977050 543670083 689348130 351856901 486127925 975367703
output:
6 207474297 171556557 0 0 888977050 543670083 689348130 351856901 733390297 40148220 24972940 254043847
result:
wrong answer Points do not come from the original point set, or are not unique