#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ep emplace_back
#define ins insert
#define fi first
#define er erase
#define se second
template<class ISqr, class T>
ISqr& operator>>(ISqr& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
#define give(v) \
cout << v << endl; \
return;
#define print(a) \
for (auto v : a) \
{ \
cout << v << " "; \
} \
cout << endl;
#define vs vector<string>
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int, int>
#define vvi vector<vector<int>>
#define sz(x) x.size()
#define vpi vector<pair<int, int>>
#define SPEED \
ios_base::sync_with_stdio(0); \
cin.tie(NULL); \
cout.tie(NULL);
#define ALL(x) x.begin(), x.end()
#define endl "\n"
#define yes cout << "YES" << endl;
#define no cout << "NO" << endl;
#define out cout << endl;
#define impos cout << -1 << endl;
#define int long long
const long double pi = 2 * acosl(0);
const int inf = 1e9;
const int mod = 1e9 + 7;
const int sz = 200001;
void solve(){
int n, m, q;
cin >> n >> m >> q;
map<int,int>f;
for(int i = 0; i <= 2*n-1; i++) f[i] = -1;
for(int i = 0; i < m; i++) {
int x; cin >> x;
f[x] = x + n;
f[x+n] = x;
}
while(q--){
int a, b;
cin >> a >> b;
if(a > b) swap(a,b);
if(f[a] == b) {
cout << 1 << endl;
continue;
}
int dis1 = min(abs(b-a), ((2*n-1)-b+a+1));
bool is = false;
if(n % 2 != 0) {
is = true;
}
if(dis1 > n/2 + is){
int r = (a + n/2) % (2*n);
int l = a - n/2;
if(l < 0) {
int sub = n/2;
sub -= a;
l = (2*n-sub);
}
if(l > r) swap(l, r);
int dis = inf;
int move = 0;
if(max(l,r) > a && min(l,r) > a) {
// 0 var
// cout << "ZOR" << endl;
for(int i = min(l,r); i > a; i--) {
// cout << i << " " << min(abs(i-a), ((2*n-1)-i+a+1)) << endl;
if(dis > min(abs(i-a), ((2*n-1)-i+a+1)) && f[i] != -1){
dis = min(abs(i-a), ((2*n-1)-i+a+1));
move = i;
}
}
// cout << "ENENENEN" << endl;
int dudus = 0;
for(int i = max(l,r); i <= 2*n-1; i++) {
// cout << i << " " << min(abs(i-a), ((2*n-1)-i+a+1)) << endl;
if(dis > min(abs(i-a), ((2*n-1)-i+a+1)) && f[i] != -1){
dis = min(abs(i-a), ((2*n-1)-i+a+1));
move = i;
}
}
// cout << "ENENENEN" << endl;
for(int i = 0; i < a; i++) {
// cout << i << " " << min(abs(i-a), ((2*n-1)-i+a+1)) << endl;
if(dis > min(abs(i-a), ((2*n-1)-i+a+1)) && f[i] != -1){
dis = min(abs(i-a), ((2*n-1)-i+a+1));
move = i;
}
}
} else {
for(int i = l; i <= r; i++) {
if(dis > min(abs(i-a), ((2*n-1)-i+a+1)) && f[i] != -1){
dis = min(abs(i-a), ((2*n-1)-i+a+1));
move = i;
}
}
}
// cout << "move: " << move << endl;
// cout << "Dis1: " << dis1 << endl;
// cout << "Dismove: " << dis << endl;
// cout << "L AND R: " << l << " " << r << endl;
if(dis == inf){
if(f[a]){
int ans = 0;
ans++;
ans += min(abs((a+n)-b), ((2*n-1)-(a+n)+b+1));
cout << min(dis1, ans) << endl;
} else{
cout << dis1 << endl;
}
}
else{
bool is = true;
if(f[move] == b) is = false;
int diss = min(abs(b-f[move]), ((2*n-1)-b+f[move]+1));
cout << min(dis1, dis+1+diss) << endl;
}
} else {
cout << dis1 << endl;
}
cout << endl << endl;
}
}
signed main() {
// freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
SPEED;
int tst = 1;
// cin >> tst;
for (int cs = 1; cs <= tst; cs++) {
solve();
}
// cerr << "Time Elapsed: " << (long double)clock() << endl;
}
Compilation message
Main.cpp: In function 'void solve()':
Main.cpp:90:21: warning: unused variable 'dudus' [-Wunused-variable]
90 | int dudus = 0;
| ^~~~~
Main.cpp:129:22: warning: variable 'is' set but not used [-Wunused-but-set-variable]
129 | bool is = true;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
3 ms |
616 KB |
Output is correct |
| 3 |
Correct |
13 ms |
648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Execution timed out |
2095 ms |
12980 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
348 KB |
Output is correct |
| 4 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
2071 ms |
728124 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
604 KB |
Output is correct |
| 2 |
Correct |
3 ms |
616 KB |
Output is correct |
| 3 |
Correct |
13 ms |
648 KB |
Output is correct |
| 4 |
Correct |
0 ms |
348 KB |
Output is correct |
| 5 |
Execution timed out |
2095 ms |
12980 KB |
Time limit exceeded |
| 6 |
Halted |
0 ms |
0 KB |
- |
