Submission #141690

#	Time	Username	Problem	Language	Result	Execution time	Memory
141690		rzbt	Robots (IOI13_robots)	C++14	90 / 100	3025 ms	55268 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#define MAXN 1000006
using namespace std;
struct igracka{
    int m,v;
    int rb;

};

igracka make_igracka(int rb,pair<int,int> a){

    igracka temp;
    temp.rb=rb;
    temp.m=a.first;
    temp.v=a.second;
    return temp;
}

bool compm(igracka a,igracka b){
    if(a.m==b.m)return a.v>b.v;
    return a.m<b.m;
}
bool compv(igracka a,igracka b){
    if(a.v==b.v)return a.m>b.m;
    return a.v<b.v;

}


bool resio[MAXN];

set<pair<int,int> > s;



pair<int,int> niz[MAXN];
int a,b,t;
int ar[50004];
int br[50004];

vector< igracka > pom;
vector< igracka > pov;

bool proveri(int v){
    s.clear();
    memset(resio,0,sizeof(resio));
    int obelezenih=0;
    int trenutna=0;
    for(int i=0;i<a;i++){

        for(;trenutna <t &&pom[trenutna].m<ar[i];trenutna++){
            s.insert(make_pair(INT_MAX-pom[trenutna].v,pom[trenutna].rb));
        }


        for(int j=0;j<v;j++){
            if(s.empty())break;
            int prvi=s.begin()->second;
            resio[prvi]=true;
            s.erase(s.begin());
            obelezenih++;

        }
    }



    trenutna=0;



    for(int i=0;i<b;i++){
        for(int j=0;j<v;j++){
            while(resio[pov[trenutna].rb] && trenutna<t)
                trenutna++;
            if(trenutna>=t)goto dalje2;

           // printf("  %d\n",pov[trenutna].rb);
            //printf("    trenutna: %d %d\n",trenutna,pov[trenutna].rb);


            if(pov[trenutna].v<br[i]){
                //printf("   resio %d sa %d\n",pov[trenutna].rb,i);
                resio[pov[trenutna].rb]=true;
                obelezenih++;
            }else{
                break;
            }

        }
    }
    dalje2:if(obelezenih==t)return true;



    return false;



}

int binarna(int l,int d,int sol){
    if(l>d)return sol;
    int mid=(l+d)/2;
    if(proveri(mid))return binarna(l,mid-1,mid);
    else return binarna(mid+1,d,sol);
}





int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[])

{
    a=B;b=A;t=T;

    for(int i=0;i<b;i++)br[i]=X[i];

    for(int i=0;i<a;i++)ar[i]=Y[i];

    sort(ar,ar+a);
    sort(br,br+b);

    for(int i=0;i<t;i++){
        niz[i].second=W[i];
        niz[i].first=S[i];
    }
    for(int i=0;i<t;i++){
        pov.push_back(make_igracka(i,niz[i]));
        pom.push_back(make_igracka(i,niz[i]));
    }
    sort(pov.begin(),pov.end(),compv);
    sort(pom.begin(),pom.end(),compm);

    /*
    printf("%d %d %d ",a,b,t);
    for(int i=0;i<a;i++)printf("%d ",ar[i]);
    for(int i=0;i<b;i++)printf("%d ",br[i]);
    for(int i=0;i<t;i++)printf("%d %d ",niz[i].first,niz[i].second);*/


    return binarna(0,MAXN-3,-1);
    printf("%d",binarna(0,MAXN-3,-1));


    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 0 / 10