QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#583272#9172. Alternating Cycleucup-team4435#WA 0ms3616kbC++205.9kb2024-09-22 19:20:582024-09-22 19:21:00

Judging History

你现在查看的是最新测评结果

  • [2024-09-22 19:21:00]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3616kb
  • [2024-09-22 19:20:58]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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