oj.uz

답안 #965681

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
965681 2024-04-19T04:48:59 Z Amr 로봇 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -