Submission #1052419

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052419		qrn	Circle Passing (EGOI24_circlepassing)	C++14	0 / 100	2095 ms	728124 KiB

Main

#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 (stderr)

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;
      |                      ^~

• Subtask 1: 0 / 14
• Subtask 2: 0 / 20
• Subtask 3: 0 / 22
• Subtask 4: 0 / 17
• Subtask 5: 0 / 27