oj.uz

Submission #1058566

# Submission time Handle Problem Language Result Execution time Memory
1058566 2024-08-14T10:59:15 Z Gray Circle Passing (EGOI24_circlepassing) C++17
31 / 100
 56 ms 13132 KB 
// #pragma GCC optimize("O3")
// #pragma GCC target("avx2")
#include <bitset>
#include <cassert>
#include <functional>
#include <map>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>
#define ll long long
#define ull unsigned ll
#define ld long double
#define ln "\n"
#define ff first
#define ss second
using namespace std;
const ll inf=2e18;
const ll MOD = 1000000007;
ll dist(ll x, ll y, ll n){
	return min(abs(x-y), 2*n-abs(x-y));
}
void solve(){
	ll n, m, q; cin >> n >> m >> q;
	vector<ll> a(2*m);
	for (ll i=0; i<m; i++){
		cin >> a[i*2];
		a[i*2+1]=a[i*2]+n;
	}
	sort(a.begin(), a.end());
	while (q--){
		ll u, v; cin >> u >> v;
		ll nind = lower_bound(a.begin(), a.end(), u)-a.begin();
		ll pind = (nind-1+2*m)%(2*m);
		cout << min(dist(u, v, n), min(1+dist(u, a[nind], n)+dist((a[nind]+n)%(2*n),v, n), 1+dist(u, a[pind], n)+dist((a[pind]+n)%(2*n), v, n))) << ln;
	}
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(nullptr);
	ll t=1;
	// cin >> t;
	while (t--) solve();
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 6 ms 924 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 860 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 51 ms 9056 KB Output is correct
4 Correct 11 ms 2652 KB Output is correct
5 Correct 3 ms 640 KB Output is correct
6 Correct 3 ms 784 KB Output is correct
7 Correct 3 ms 720 KB Output is correct
8 Correct 3 ms 604 KB Output is correct
9 Correct 3 ms 788 KB Output is correct
10 Correct 3 ms 840 KB Output is correct
11 Correct 3 ms 860 KB Output is correct
12 Correct 3 ms 704 KB Output is correct
13 Correct 3 ms 860 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 27 ms 6224 KB Output is correct
16 Correct 28 ms 5732 KB Output is correct
17 Correct 56 ms 13124 KB Output is correct
18 Correct 56 ms 13132 KB Output is correct
19 Correct 0 ms 348 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 344 KB Output is correct
2 Correct 3 ms 348 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 3 ms 720 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 6 ms 924 KB Output is correct
8 Correct 4 ms 860 KB Output is correct
9 Correct 4 ms 860 KB Output is correct
10 Correct 4 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Incorrect 0 ms 348 KB Output isn't correct
15 Halted 0 ms 0 KB -