Submission #473036

#	Time	Username	Problem	Language	Result	Execution time	Memory
473036		nicolaalexandra	Watching (JOI13_watching)	C++14	50 / 100	1088 ms	45804 KiB

watching

#include <bits/stdc++.h>
#define DIM 2010
#define INF 1000000000
using namespace std;

struct idk{
    int poz,p,q;
};
deque <idk> c;
int v[DIM];
map <pair<int,pair<int,int> >, int> viz;
int n,p,q,i;

int get_poz (int x){
    int st = 1, dr = n, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (v[mid] <= x){
            sol = mid;
            st = mid+1;
        } else dr = mid-1;
    }
    return sol;
}

int verif (int val){

    int poz1 = get_poz (v[1] + val - 1);
    int poz2 = get_poz (v[1] + 2 * val - 1);

    c.clear(),viz.clear();
    c.push_back({poz1,p-1,q});
    c.push_back({poz2,p,q-1});

    viz[make_pair(poz1,make_pair(p-1,q))] = 1;
    viz[make_pair(poz2,make_pair(p,q-1))] = 1;
    //viz[poz1][p-1][q] = 1;
    //viz[poz2][p][q-1] = 1;

    while (!c.empty()){
        int poz = c.front().poz;
        int p = c.front().p;
        int q = c.front().q;
        c.pop_front();

        if (poz == n)
            return 1;

        if (p){
            int new_poz = get_poz (v[poz+1] + val - 1);
            if (!viz[make_pair(new_poz,make_pair(p-1,q))]){
                viz[make_pair(new_poz,make_pair(p-1,q))] = 1;
                c.push_back({new_poz,p-1,q});
            }
        }

        if (q){
            int new_poz = get_poz (v[poz+1] + 2 * val - 1);
            if (!viz[make_pair(new_poz,make_pair(p,q-1))]){
                viz[make_pair(new_poz,make_pair(p,q-1))] = 1;
                c.push_back({new_poz,p,q-1});
            }
        }
    }

    return 0;
}

int main (){

    //ifstream cin ("date.in");
    //ofstream cout ("date.out");

    cin>>n>>p>>q;
    for (i=1;i<=n;i++)
        cin>>v[i];

    sort (v+1,v+n+1);
    p = min (p,n), q = min (q,n);

    int st = 0, dr = INF, sol = 0;
    while (st <= dr){
        int mid = (st+dr)>>1;
        if (verif(mid)){
            sol = mid;
            dr = mid-1;
        } else st = mid+1;
    }

    cout<<sol;

    return 0;
}

• Subtask 1: 50 / 50
• Subtask 2: 0 / 50