oj.uz

Submission #968859

# Submission time Handle Problem Language Result Execution time Memory
968859 2024-04-24T07:51:41 Z anango Robots (IOI13_robots) C++17
14 / 100
 1519 ms 16940 KB 
#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;
    priority_queue<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.push(sortedbyx[pointer].second);
            pointer++;
        }
        while (ct<time && leftvalues.size()) {
            leftvalues.pop();
            ct++;
        }  
        
    }
    while (pointer<t) {
        leftvalues.push(sortedbyx[pointer].second);
        pointer++;

    }
    
    int work=1;
    vector<int> normalvalues; //y values
    while (leftvalues.size()) {
        normalvalues.push_back(leftvalues.top());
        leftvalues.pop();
    }
    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 (i==b-1 && r>0) {
            return 0;
        }
        if (r/((b-i-1))>time || r/((b-i-1))==time && r%(b-i-1)!=0) {
            //cout <<"BSTA" <<" " << time <<" " << 0 << endl;
            return 0;
        }
    }
    if (normalvalues.size() > b*time) {
        return 0;
    }
    //cout <<"BSTA" <<" " << time <<" " << 1;
    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]);
    }
    sort(wv.begin(), wv.end());
    sort(sv.begin(), sv.end());
    for (int i=0; i<T; i++) {
        //cout << i <<" " << mw << " " << ms <<" " << W[i] <<" " << S[i] << endl;
        if (W[i] >= mw && S[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

robots.cpp: In function 'bool BSTA(int)':
robots.cpp:59:51: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   59 |         if (r/((b-i-1))>time || r/((b-i-1))==time && r%(b-i-1)!=0) {
      |                                 ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
robots.cpp:64:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   64 |     if (normalvalues.size() > b*time) {
      |         ~~~~~~~~~~~~~~~~~~~~^~~~~~~~
robots.cpp:38:9: warning: unused variable 'work' [-Wunused-variable]
   38 |     int work=1;
      |         ^~~~
robots.cpp:50:9: warning: unused variable 'cur' [-Wunused-variable]
   50 |     int cur=0;
      |         ^~~
robots.cpp:51:9: warning: unused variable 'lastr' [-Wunused-variable]
   51 |     int lastr=0;
      |         ^~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:89:15: warning: variable 'i' set but not used [-Wunused-but-set-variable]
   89 |     for (auto i:sortedbyx) {
      |               ^

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Runtime error 4 ms 8796 KB Execution killed with signal 8
3 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 1118 ms 16432 KB Output is correct
5 Correct 126 ms 14552 KB Output is correct
6 Correct 24 ms 5856 KB Output is correct
7 Correct 269 ms 14552 KB Output is correct
8 Correct 785 ms 16132 KB Output is correct
9 Correct 1519 ms 16940 KB Output is correct

Subtask #3
0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 8796 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 8796 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 8792 KB Execution killed with signal 8
2 Halted 0 ms 0 KB -