oj.uz

Submission #965672

# Submission time Handle Problem Language Result Execution time Memory
965672 2024-04-19T04:31:58 Z Amr Robots (IOI13_robots) C++17
39 / 100
 3000 ms 25424 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  = 2e5+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(xx,xx+n1);
    sort(yy,yy+n2);
    ll l = 0, r = 1;
    while(!good(r)&&r<5e6) r*=2;
    while(l+1<r)
    {
        ll mid = (l+r)/2;
        if(good(mid)) r = mid;
        else l = mid;
    }
    if(r>5e6) return -1; else return r;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 2 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 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct
3 Correct 2 ms 6492 KB Output is correct
4 Execution timed out 3044 ms 25292 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 6492 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 2 ms 6492 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6492 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 6588 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct
11 Correct 1 ms 6596 KB Output is correct
12 Correct 1 ms 6592 KB Output is correct
13 Correct 1 ms 6488 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct

Subtask #4
0 / 37.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 Correct 1 ms 6748 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
8 Correct 1 ms 6492 KB Output is correct
9 Correct 1 ms 6492 KB Output is correct
10 Correct 1 ms 6500 KB Output is correct
11 Correct 1 ms 6748 KB Output is correct
12 Correct 1 ms 6488 KB Output is correct
13 Correct 1 ms 6492 KB Output is correct
14 Correct 1 ms 6492 KB Output is correct
15 Correct 1 ms 6492 KB Output is correct
16 Correct 1571 ms 7008 KB Output is correct
17 Correct 1543 ms 7004 KB Output is correct
18 Execution timed out 3094 ms 7004 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 1 ms 6492 KB Output is correct
3 Correct 1 ms 6492 KB Output is correct
4 Correct 1 ms 6592 KB Output is correct
5 Correct 1 ms 6492 KB Output is correct
6 Correct 1 ms 6596 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 3064 ms 25424 KB Time limit exceeded
11 Halted 0 ms 0 KB -