oj.uz

Submission #1109843

# Submission time Handle Problem Language Result Execution time Memory
1109843 2024-11-07T19:19:20 Z Raj Circle Passing (EGOI24_circlepassing) C++11
0 / 100
 2000 ms 36656 KB 
#include <bits/stdc++.h>
using namespace std;
int n,M,Q;
set <int> s;
int dist(int x,int y)
{
    return min(abs(x-y),n*2-abs(x-y));
}
int shc(int x, int y)
{
    int vst,vdr;
    if(upper_bound(s.begin(),s.end(),x)==s.end())
        vdr=*s.begin();
    else
        vdr=*upper_bound(s.begin(),s.end(),x);
    
    if(lower_bound(s.begin(),s.end(),x)!=s.end())
    {
        if(*lower_bound(s.begin(),s.end(),x)==x)
            vst=x;
        else
        {   
            if(lower_bound(s.begin(),s.end(),x)==s.begin())
                vst=*s.rbegin();
            else
                vst=*--upper_bound(s.begin(),s.end(),x);
        }
    }
    else
    {
        auto it=lower_bound(s.begin(),s.end(),x);
        --it;
        vst=*lower_bound(s.begin(),s.end(),x);
    }
    int prst,prdr;
    if(vst>4)
        prst=vst-n;
    else
        prst=vst+n;
    if(vdr>4)
        prdr=vdr-n;
    else
        prdr=vdr+n;    
    int d1=dist(x,y);
    int d2=dist(x,vst)+1+dist(prst,y);
    int d3=dist(x,vdr)+1+dist(prdr,y);
    return min(d1,min(d2,d3));
}
int main()
{
    cin>>n>>M>>Q;
    for(int i=1;i<=M;++i)
    {
        int x;
        cin>>x;
        if(x>n)
            s.insert(2*n-x);
        else
            s.insert(x+n);
        s.insert(abs(x));
    }
    for(int i=1;i<=Q;++i)
    {
        int a,b;
        cin>>a>>b;
        cout<<shc(a,b)<<'\n';
    }
    return 0;
}

Subtask #1
0.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 676 KB Output is correct
2 Incorrect 35 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 504 KB Output is correct
2 Incorrect 3 ms 336 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 1 ms 504 KB Output is correct
2 Incorrect 3 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 836 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Execution timed out 2072 ms 36656 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 676 KB Output is correct
2 Incorrect 35 ms 336 KB Output isn't correct
3 Halted 0 ms 0 KB -