oj.uz

Submission #965681

# Submission time Handle Problem Language Result Execution time Memory
965681 2024-04-19T04:48:59 Z Amr Robots (IOI13_robots) C++17
76 / 100
 3000 ms 18528 KB 
#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define sz size()
#define all(x) (x).begin(),(x).end()
const int N  = 1e6+2;
vector<pair<ll,ll> > v;
ll n1, n2 , n;
ll xx[N],yy[N];
bool cmp(pair<ll,ll> a, pair<ll,ll> b)
{
    return a.S > b.S;
}
bool cmp2(pair<ll,ll> a, pair<ll,ll> b)
{
    return a.S < b.S;
}

bool good(ll x)
{

    sort(all(v));
    ll lst = 0;
    for(int i = 0; i < n1; i++)
    {
        pair<ll,ll> p = {xx[i],0};
       ll pos = (lower_bound(v.begin(),v.end(),p)-v.begin());
        pos--;
        if(pos<lst) continue;
        //reverse(v.begin()+lst,v.begin()+pos+1);
        sort(v.begin()+lst,v.begin()+pos+1,cmp);
        lst = max(lst,min(pos+1,lst+x));
        //if(lst!=pos+1) sort(v.begin()+lst,v.begin()+pos+1);

     //   cout << pos << " ";
    }

    if(lst!=n)
    sort(v.begin()+lst,v.begin()+n,cmp2);
    for(int i = 0; i < n2; i++)
    {
        ll cnt = 0;
        while(cnt<x&&lst<n&&v[lst].S<yy[i]) cnt++,lst++;

    }
    return (lst==n);
}
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    n = T , n1 = A , n2 = B;
    v.resize(n);
    for(int i = 0; i < A; i++) xx[i] = X[i];
    for(int i = 0; i < B; i++) yy[i] = Y[i];
    for(int i = 0; i < n; i++) v[i] = {W[i],S[i]};
    sort(all(v));
    sort(xx,xx+n1);
    sort(yy,yy+n2);
    if(good(n)==0) return -1;
    ll l = 0, r = n;
    //while(!good(r)) r*=2;

    while(l+1<r)
    {
        ll mid = (l+r)/2;
        if(good(mid)) r = mid;
        else l = mid;
    }
    return r;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 6488 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 6488 KB Output is correct
6 Correct 1 ms 6492 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Execution timed out 3099 ms 18476 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 2 ms 8540 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6488 KB Output is correct
9 Correct 1 ms 6488 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8536 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 1 ms 8640 KB Output is correct
16 Correct 340 ms 8796 KB Output is correct
17 Correct 240 ms 8796 KB Output is correct
18 Correct 655 ms 8856 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 6492 KB Output is correct
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Execution timed out 3048 ms 18528 KB Time limit exceeded
11 Halted 0 ms 0 KB -