Submission #968845

#	Time	Username	Problem	Language	Result	Execution time	Memory
968845		anango	Robots (IOI13_robots)	C++17	0 / 100	2 ms	4596 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>

using namespace std;
int a,b,t;
vector<pair<int,int>> sortedbyx;
vector<int> xv;
vector<int> yv;
vector<int> wv;
vector<int> sv;

bool BSTA(int time) {
    //cout << "BSTA" << " " << time << endl;
    multiset<int> leftvalues;
    int pointer=0;
    //start by placing the vertical dividers
    for (int i=0; i<a; i++) {
        int val=wv[i];
        int ct=0;
        //put into the set as {y,x}
        while (pointer<t && sortedbyx[pointer].first < val) {
            //cout <<pointer <<"  " << "INSERTING " << -sortedbyx[pointer].second << endl;
            leftvalues.insert(-sortedbyx[pointer].second);
            pointer++;
        }
        while (ct<time && leftvalues.size()) {
            leftvalues.erase(leftvalues.begin());
            ct++;
        }  
        
    }
    while (pointer<t) {
        leftvalues.insert(-sortedbyx[pointer].second);
        pointer++;

    }
    
    int work=1;
    vector<int> normalvalues; //y values
    for (auto i:leftvalues) {
        normalvalues.push_back(-i);
    }
    sort(normalvalues.begin(), normalvalues.end());

    /*for (auto i:normalvalues) {
        cout << i << " ";
    }
    cout << endl;*/
    int cur=0;
    int lastr=0;
    for (int i=0; i<b; i++) {
        int r=lower_bound(normalvalues.begin(), normalvalues.end(), sv[i])-normalvalues.begin();
        r=normalvalues.size()-r;
        //cout <<"megabloat " <<  i <<" " << sv[i] <<" " << r << endl;
        if (r>(b-i-1)*time) {
            return 0;
        }
        lastr=r;
    }
    return 1;
    


}

int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    
    a=A;
    b=B;
    t=T;
    xv=vector<int>(T,-1);
    yv=vector<int>(T,-1);
    wv=vector<int>(A,-1);
    sv=vector<int>(B,-1);
    for (int i=0; i<T; i++) {
        xv[i] = W[i];
        yv[i] = S[i];
        sortedbyx.push_back({W[i], S[i]});  
    }
    sort(sortedbyx.begin(), sortedbyx.end());
    for (auto i:sortedbyx) {
        //cout << i.first <<" " << i.second << endl;
    }
    int mw=0;
    int ms=0;
    for (int i=0; i<A; i++) {
        wv[i] = X[i];
        mw=max(mw,X[i]);
    }
    for (int i=0; i<B; i++) {
        sv[i] = Y[i];
        ms=max(ms,Y[i]);
    }
    for (int i=0; i<T; i++) {
        if (X[i] >= mw && Y[i] >= ms) {
            return -1;
        }
    }
    int l=1;
    int r=T*2;
    while (l<r) {
        int m=(l+r)/2;
        int bst=BSTA(m);
        //cout << l <<" " << r << " " << m <<" " << bst << endl;
        if (bst) {
            l=l;
            r=m;
        }
        else {
            l=m+1;
            r=r;
        }
    }
    if (l>0 && BSTA(l-1)) {
        l--;
    }
    if (!BSTA(l)) {
        l++;
    }
    if (l>T) {
        return -1;
    }
    return l;
}

Compilation message (stderr)

robots.cpp: In function 'bool BSTA(int)':
robots.cpp:38:9: warning: unused variable 'work' [-Wunused-variable]
   38 |     int work=1;
      |         ^~~~
robots.cpp:49:9: warning: unused variable 'cur' [-Wunused-variable]
   49 |     int cur=0;
      |         ^~~
robots.cpp:50:9: warning: variable 'lastr' set but not used [-Wunused-but-set-variable]
   50 |     int lastr=0;
      |         ^~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:81:15: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   81 |     for (auto i:sortedbyx) {
      |               ^

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