oj.uz

Submission #225712

# Submission time Handle Problem Language Result Execution time Memory
225712 2020-04-21T11:36:41 Z SorahISA Svjetlost (COI18_svjetlost) C++17
0 / 100
 3000 ms 1520 KB 
// #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.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1408 KB 1st numbers differ - expected: '34724.8554753593', found: '34055.3370017000', error = '0.0192806698'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1408 KB 1st numbers differ - expected: '34724.8554753593', found: '34055.3370017000', error = '0.0192806698'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1408 KB 1st numbers differ - expected: '32934.3604541195', found: '32374.7182925800', error = '0.0169926531'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3077 ms 1520 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1408 KB 1st numbers differ - expected: '34724.8554753593', found: '34055.3370017000', error = '0.0192806698'
2 Halted 0 ms 0 KB -