Submission #846396

#	Time	Username	Problem	Language	Result	Execution time	Memory
846396		vjudge1	OGLEDALA (COI15_ogledala)	C++17	41 / 100	133 ms	43280 KiB

ogledala

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

using ll = long long;
using ld = long double;
#define pb push_back
#define endl '\n'
#define fi first
#define se second
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);
#define CDIV(a,b) (((a)+(b)-(1))/(b))
const ll inf = 1e17 + 5;
const ll mod = 1e9 + 7;
const ll N = 3e5 + 30;

 
ll mod_(ll a, ll b)
{
    if(a >= 0)return a % b;
    a += (-a/b + 1) * b;
    return a % b;
}

const ll maxq = 3e5 + 5;

void solve()
{
    ll m, n, q;
    cin >> m >> n >> q;
    ll last = 1;
    set<array<ll, 3> >s;
    vector<ll>ans(maxq + 1);
    for(ll i = 0; i < n; ++i)
    {
        ll r;
        cin >> r;
        s.insert({-(r - last), last, r - 1});
        last = r + 1;
        ans[i + 1] = r;
    }
    if(last <= m)s.insert({-(m - last + 1),last, m});
    for(ll i = n + 1; i <= maxq and !s.empty(); ++i)
    {
        //cout << i << ' ';
        array<ll, 3> a = *s.begin();
        a[0] = -a[0];
        //for(ll j : a)cout << j << ' ';
        s.erase(s.begin());
        ans[i] = (a[2] + a[1])/2;
        //cout << " ans : " << ans[i] << endl;
        if(a[0] > 2)
        {
            s.insert({-(ans[i] - a[1]), a[1], ans[i] - 1});
            s.insert({-(a[2] - ans[i]), ans[i] + 1, a[2]});
        }
        else if(a[0] == 2)
        {
            s.insert({-(a[2] - ans[i]), ans[i] + 1, a[2]});
        }
    }
    while(q--)
    {
        ll idx;
        cin >> idx;
        cout << ans[idx] << endl;
    }
    
}


int main()
{
    fio;
    //nt t; cin >> t; while(t--)
    {
        solve();
    }
}

• Subtask 1: 19 / 19
• Subtask 2: 22 / 22
• Subtask 3: 0 / 59