Submission #225712

#	Time	Username	Problem	Language	Result	Execution time	Memory
225712		SorahISA	Svjetlost (COI18_svjetlost)	C++17	0 / 100	3077 ms	1520 KiB

Main

// #pragma GCC target("avx2")
#pragma GCC optimize("O3", "unroll-loops")

// #include <bits/extc++.h>
// using namespace __gnu_pbds;

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double
// template <typename T>
// using pbds_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using pii = pair<int, int>;
template<typename T>
using prior = priority_queue<T, vector<T>, greater<T>>;
template<typename T>
using Prior = priority_queue<T>;

#define X first
#define Y second
#define ALL(x) (x).begin(), (x).end()
#define eb emplace_back
#define pb push_back

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define RANDOM() random_device __rd; \
                 mt19937 __gen = mt19937(__rd()); \
                 uniform_int_distribution<int> __dis(0, 1); \
                 auto rnd = bind(__dis, __gen);

const int INF = 1E18;
const int mod = 1E9 + 7;
const int maxn = 1 << 17;

int n, q;
vector<pii> point;
vector<int> BIT(maxn, 0);

void Add(int idx) {
    while (idx < maxn) ++BIT[idx], idx += idx&-idx;
}

int Sum(int idx, int ans = 0) {
    while (idx) ans += BIT[idx], idx -= idx&-idx;
    return ans;
}

int MOD(int val, int mod) {
    return (val % mod + mod) % mod;
}

int point_dot(pii o, pii a, pii b) {
    return (a.X-o.X) * (b.X-o.X) + (a.Y-o.Y) * (b.Y-o.Y);
}

double point_dis(pii a, pii b) {
    return sqrt((a.X-b.X) * (a.X-b.X) + (a.Y-b.Y) * (a.Y-b.Y));
}

void cal_ans() {
    int opp = 0;
    double ans = 0.0;
    for (int i = 0; i < n; ++i) {
        int tmpA = point_dot(point[i], point[MOD(i-1, n)], point[opp]);
        int tmpB = point_dot(point[opp], point[MOD(opp+1, n)], point[i]);
        
        while (!(tmpA >= 0 and tmpB >= 0 and !(tmpA == 0 and tmpB == 0))) {
            opp = MOD(opp+1, n);
            tmpA = point_dot(point[i], point[MOD(i-1, n)], point[opp]);
            tmpB = point_dot(point[opp], point[MOD(opp+1, n)], point[i]);
        }
        
        double tmp = 0.0;
        for (int j = opp; j != i; j = MOD(j+1, n)) {
            tmp += point_dis(point[MOD(j+1, n)], point[j]);
        }
        
        ans = max(ans, tmp);
    }
    
    cout << fixed << setprecision(8) << ans << "\n";
}

int32_t main() {
    fastIO();
    
    cin >> n, point.resize(n);
    for (auto &[x, y] : point) cin >> x >> y;
    cal_ans();
    
    cin >> q;
    for (int i = 0; i < q; ++i) {
        int p; cin >> p, Add(p), p -= Sum(p-1), --p, --n;
        for (int i = p; i < n; ++i) point[i] = point[i+1];
        point.resize(n);
        cal_ans();
    }
    
    return 0;
}

• Subtask 1: 0 / 12
• Subtask 2: 0 / 14
• Subtask 3: 0 / 14
• Subtask 4: 0 / 29
• Subtask 5: 0 / 31