Submission #1065108

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065108		sunboi	Circle Passing (EGOI24_circlepassing)	C++17	100 / 100	361 ms	52816 KiB

Main

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

 
 signed main(){
    int n, m, q; cin >> n >> m >> q;
    set<int> val;
    for (int i = 0; i < m; i++){
        int x; cin >> x;
        val.insert(x);
        if (x <= n - 1) val.insert(x + n);
        else val.insert(x - n);
    }
    while(q--){
        int x, y; cin >> x >> y;
        if (x > y) swap(x, y);
        int ans = min(y- x, 2 * n - y + x);
        auto it = val.upper_bound(x);
        if (it != val.end()){
            int new_x = *it;
            int extra = abs(new_x - x);
            
            if (*it >= n) new_x -= n;
            else new_x += n;
            
            int new_y = y;
            if (new_x > new_y) swap(new_x, new_y);
            ans = min(ans, new_y - new_x + 1 + extra);
            ans = min(ans, 2 * n - new_y + new_x + 1 + extra);
        }
        if (it != val.begin()){
            it--;
            int new_x = *it;
            int extra = abs(new_x - x);
            
            if (*it >= n) new_x -= n;
            else new_x += n;
            
            int new_y = y;
            if (new_x > new_y) swap(new_x, new_y);
            ans = min(ans, new_y - new_x + 1 + extra);
            ans = min(ans, 2 * n - new_y + new_x + 1 + extra);
        }
        
        if (!val.empty()){
            auto it = val.begin();
            int new_x = *it;
            int extra = min(2 * n - abs(new_x - x),abs(new_x - x));
            
            if (*it >= n) new_x -= n;
            else new_x += n;
            
            int new_y = y;
            if (new_x > new_y) swap(new_x, new_y);
            ans = min(ans, new_y - new_x + 1 + extra);
            ans = min(ans, 2 * n - new_y + new_x + 1 + extra);
        }
        
        if (!val.empty()){
            auto it = val.end();
            it--;
            int new_x = *it;
            int extra = min(2 * n - abs(new_x - x),abs(new_x - x));
            
            if (*it >= n) new_x -= n;
            else new_x += n;
            
            int new_y = y;
            if (new_x > new_y) swap(new_x, new_y);
            ans = min(ans, new_y - new_x + 1 + extra);
            ans = min(ans, 2 * n - new_y + new_x + 1 + extra);
        }
        
        cout << ans << endl;
    }
    
    
    
    
    
    
 }

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