Submission #846419

#	Time	Username	Problem	Language	Result	Execution time	Memory
846419		vjudge1	OGLEDALA (COI15_ogledala)	C++17	19 / 100	201 ms	51480 KiB

ogledala

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define pri pair<int,int>
#define prl pair<ll,ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pair<int,int>>
#define vpl vector<pair<ll,ll>>
#define re return 0
#define sqrt sqrtl

struct segment {
    int l;
    int r;
};

inline bool operator<(const segment& lhs, const segment& rhs)
{
    if (lhs.r-lhs.l == rhs.r-rhs.l) return lhs.l<rhs.l;
    return lhs.r-lhs.l > rhs.r-rhs.l;
}

int32_t main() {
    int m,n,q;cin>>m>>n>>q;
    vi a(n);for (int i = 0;i<n;i++) cin>>a[i];
    a.push_back(m+1);
    int l = 0;
    set<segment> pq;
    for (int i = 0;i<n+1;i++) {
        pq.insert(segment{l+1,a[i]-1});
        l=a[i];
    }
    deque<int> queries(q); for(int i = 0;i<q;i++) cin>>queries[i];
    int qc = 0;
    int c = n+1;
    while (1) {
        int f = queries[0];
        if (f<n+1) cout<<a[f-1]<<endl;
        else break;
        queries.pop_front();
    }
    while (qc<queries.size()) {

        auto f = *pq.begin();
        pq.erase(pq.begin());
        int curr;
        if ((f.r-f.l)%2) {
            if (f.r+2 == f.l) {
                pq.insert({f.l + 1,f.l+1});
                curr = f.l;
            } else {
                pq.insert({f.l, (f.r+f.l)/2-1});
                pq.insert({(f.r+f.l)/2+1,f.r});
                curr = (f.r+f.l)/2;
            }
        } else {
            if (f.r!=f.l) {
                pq.insert({f.l,(f.l+f.r)/2-1});
                pq.insert({(f.l+f.r)/2+1,f.r});
                curr = (f.l+f.r)/2;
            } else curr = f.l;
        }
        if (c==queries[qc]) {
            cout<<curr<<endl;
            qc++;
            c++;
        } else {c++;}
    }
    return 0;
}

Compilation message (stderr)

ogledala.cpp: In function 'int32_t main()':
ogledala.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |     while (qc<queries.size()) {
      |            ~~^~~~~~~~~~~~~~~

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