oj.uz

Submission #232920

# Submission time Handle Problem Language Result Execution time Memory
232920 2020-05-18T16:34:00 Z shayan_p Svjetlost (COI18_svjetlost) C++14
40 / 100
 3000 ms 2296 KB 
// Never let them see you bleed...

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

pll p[maxn];

ll operator * (pll a, pll b){
    return a.F * b.S - a.S * b.F;   
}
ll operator ^ (pll a, pll b){
    return a.F * b.F + a.S * b.S;
}
pll operator + (pll a, pll b){
    return {a.F + b.F, a.S + b.S};
}
pll operator - (pll a, pll b){
    return {a.F - b.F, a.S - b.S};
}

double lnn(pll a, pll b){
    return sqrt((a-b) ^ (a-b));
}

int n;
int nxt[maxn], bef[maxn];

void solve(int st){
    int l = st, r = st;
    double len = 0, ans = 0;
    do{
	if(r == l)
	    r = nxt[r], len+= lnn(p[l], p[r]);
	while(l != r && (p[nxt[l]] - p[l]) * (p[nxt[r]] - p[r]) > 0)
	    len+= lnn(p[r], p[nxt[r]]), r = nxt[r];
	ans = max(ans, len);
	len-= lnn(p[l], p[nxt[l]]);
	l = nxt[l];
    }while(l != st);
    cout << setprecision(7) << fixed << ans << "\n";
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie();

    cin >> n;
    for(int i = 0; i < n; i++){
	cin >> p[i].F >> p[i].S;
	nxt[i] = (i+1) % n;
	bef[i] = (i+n-1) % n;
    }
    solve(0);
    int q;
    cin >> q;
    while(q--){
	int x;
	cin >> x;
	--x;
	int A = bef[x], B = nxt[x];
	bef[B] = A, nxt[A] = B;
	solve(A);
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 4 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 4 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 7 ms 384 KB 101 numbers
6 Correct 24 ms 384 KB 1201 numbers
7 Correct 34 ms 504 KB 1556 numbers
8 Correct 50 ms 384 KB 1996 numbers
9 Correct 46 ms 384 KB 1960 numbers
10 Correct 47 ms 384 KB 1991 numbers
11 Correct 47 ms 384 KB 1963 numbers

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
2 Correct 5 ms 384 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
3 Correct 7 ms 640 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
4 Correct 11 ms 896 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
5 Correct 30 ms 2296 KB found '3142086769.6889634132', expected '3142086769.6889681816', error '0.0000000000'
6 Correct 29 ms 2296 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 384 KB 1001 numbers
2 Execution timed out 3083 ms 1184 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB 11 numbers
2 Correct 4 ms 384 KB 41 numbers
3 Correct 4 ms 384 KB 11 numbers
4 Correct 5 ms 384 KB 93 numbers
5 Correct 7 ms 384 KB 101 numbers
6 Correct 24 ms 384 KB 1201 numbers
7 Correct 34 ms 504 KB 1556 numbers
8 Correct 50 ms 384 KB 1996 numbers
9 Correct 46 ms 384 KB 1960 numbers
10 Correct 47 ms 384 KB 1991 numbers
11 Correct 47 ms 384 KB 1963 numbers
12 Correct 5 ms 384 KB found '32934.3604541000', expected '32934.3604541195', error '0.0000000000'
13 Correct 5 ms 384 KB found '31571636.3365448005', expected '31571636.3365447633', error '0.0000000000'
14 Correct 7 ms 640 KB found '31442617.6286691017', expected '31442617.6286691241', error '0.0000000000'
15 Correct 11 ms 896 KB found '31424400.0534065999', expected '31424400.0534067489', error '0.0000000000'
16 Correct 30 ms 2296 KB found '3142086769.6889634132', expected '3142086769.6889681816', error '0.0000000000'
17 Correct 29 ms 2296 KB found '3142076120.8714442253', expected '3142076120.8714694977', error '0.0000000000'
18 Correct 47 ms 384 KB 1001 numbers
19 Execution timed out 3083 ms 1184 KB Time limit exceeded
20 Halted 0 ms 0 KB -