QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#583272 | #9172. Alternating Cycle | ucup-team4435# | WA | 0ms | 3616kb | C++20 | 5.9kb | 2024-09-22 19:20:58 | 2024-09-22 19:21:00 |
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;
}
};
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());
void solve() {
int n;
cin >> n;
A.resize(n);
rep(i, n) cin >> A[i].x >> A[i].y;
shuffle(all(A), rng);
for (int s = 5; s < n; ++s) {
if (clock() / 1.0 * CLOCKS_PER_SEC >= 1.8) {
break;
}
for (int i = 0; i < s; ++i) {
for (int st = 1; st <= 2; ++st) {
vector<vector<vi>> dp(1 << s, vector<vi>(s, vi(s, 0)));
rep(j, s) {
if (i == j) continue;
int q = ang_type(s, i, j);
if (q != st) continue;
dp[(1 << i) | (1 << j)][j][i] |= q;
}
ar<int, 4> answer = {-1, -1, -1, -1};
rep(mask, 1 << s) {
if (__builtin_popcount(mask) > 5) continue;
rep(last, s) {
rep(plast, s) {
if (!dp[mask][last][plast]) continue;
rep(nxt, s + 1) {
if ((1 << nxt) & mask) continue;
int v = ang_type(plast, last, nxt);
assert(v);
if (dp[mask][last][plast] & (v ^ 3)) {
if (nxt == s) {
if (v != st) continue;
if (ang_type(last, s, i) == st) continue;
answer = {mask, last, plast, v ^ 3};
break;
}
dp[mask | (1 << nxt)][nxt][last] |= v;
}
}
if (answer[0] != -1) break;
}
if (answer[0] != -1) break;
}
if (answer[0] != -1) break;
}
if (answer[0] == -1) continue;
vi p;
int mask = answer[0];
int last = answer[1];
int plast = answer[2];
int v = answer[3];
while (__builtin_popcount(mask) != 2) {
assert(dp[mask][last][plast] & v);
p.push_back(last);
mask ^= (1 << last);
bool ok = false;
rep(pplast, s) {
if (((1 << pplast) & mask) && pplast != plast) {
int tv = ang_type(pplast, plast, last);
if (tv != v) continue;
if (dp[mask][plast][pplast] & (tv ^ 3)) {
ok = true;
last = plast;
plast = pplast;
v ^= 3;
break;
}
}
}
assert(ok);
}
p.push_back(last);
p.push_back(plast);
p.push_back(s);
reverse(all(p));
assert(p.size() % 2 == 0);
assert(p.size() == 6);
cout << p.size() << '\n';
rep(t, p.size()) {
cout << A[p[t]].x << ' ' << A[p[t]].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: 0
Wrong Answer
time: 0ms
memory: 3616kb
input:
6 10 15 20 15 15 23 0 31 15 0 30 30
output:
-1
result:
wrong answer Jury has a better answer