Submission #1301753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301753		rana_azka	Circle Passing (EGOI24_circlepassing)	C++20	31 / 100	442 ms	71032 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int INF = 1e18;
const int MOD = 1e9+7;
const int MAXN = 1e5;

int n, m, q;
vector<int> punyaBF;
map<int, int> BF;

void mulaidarinol(){}

int getDist(int a, int b){
    if(a > b) swap(a, b);

    int ret = min(b - a, (2*n) - b + a);
    return ret;
}

void solve(){
    cin >> n >> m >> q;
    for(int i = 1; i <= m; i++){
        int x; cin >> x;
        punyaBF.push_back(x);
        punyaBF.push_back(x+n);
        BF[x] = x+n;
        BF[x+n] = x;
    }

    sort(punyaBF.begin(), punyaBF.end());
    reverse(punyaBF.begin(), punyaBF.end());
    punyaBF.push_back(punyaBF[0]);
    reverse(punyaBF.begin(), punyaBF.end());

    while(q--){
        int start, finish; cin >> start >> finish;

        int ans = getDist(start, finish);

        int idx;
        int left = 1, right = 2*m;
        int mid;
        while(left <= right){
            mid = (left + right) / 2;
            if(punyaBF[mid] >= start){
                idx = mid;
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }

        int temp1 = getDist(start, punyaBF[idx]) + 1 + getDist(BF[punyaBF[idx]], finish);
        int temp2 = getDist(start, punyaBF[idx-1]) + 1 + getDist(BF[punyaBF[idx-1]], finish);
        ans = min(min(temp1, temp2), ans);

        cerr << "=> ";
        cout << ans << endl;
    }
}

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

    int tc = 1;
    // cin >> tc;
    while(tc--){
        // mulaidarinol();
        solve();
        // cerr << endl;
    }

    return 0;
}

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