oj.uz

Submission #28002

# Submission time Handle Problem Language Result Execution time Memory
28002 2017-07-14T15:35:56 Z repeating Robots (IOI13_robots) C++11
76 / 100
 1883 ms 64728 KB 
#include <bits/stdc++.h>
#include "robots.h"
#define F first
#define S second
#define P push
#define pb push_back
#define MEM(dp,i) memset(dp,i,sizeof(dp))
#define W while
#define R return
#define C continue
#define SI size()
#define ll long long
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define SF(x) scanf("%I64d",&x)
#define SF2(x,y) scanf("%I64d%I64d",&x,&y)
#define SF3(x,y,z) scanf("%I64d%I64d%I64d",&x,&y,&z)
#define SF4(x,y,z,o) scanf("%I64d%I64d%I64d%I64d",&x,&y,&z,&o)
#define all(v) v.begin(),v.end()

using namespace std;
const long long INF = 1e9;
const int MX=1000005;

vector<int> v1,v2;
int n,A,B,X[50005],Y[50005],w[MX],s[MX];
bool cmp1(int a,int b){
    if(w[a]==w[b])R s[a]>s[b];
    R w[a]<w[b];
}
bool cmp2(int a,int b){
    if(s[a]==s[b])R w[a]>w[b];
    R s[a]<s[b];
}
int seg1[MX*4],seg2[MX*4];
int ind1[MX],ind2[MX];
int sum=0;
void u1(int node,int l,int r,int ind,int val){
    if(ind<l||r<ind)R;
    if(l==r){
        seg1[node]=val;
        R;
    }
    u1(node*2,l,(l+r)/2,ind,val);
    u1(node*2+1,(l+r)/2+1,r,ind,val);
    if(seg1[node*2]==n&&seg1[node*2+1]==n){
        seg1[node]=n;
        R;
    }
    if(s[seg1[node*2]]>s[seg1[node*2+1]])
        seg1[node]=seg1[node*2];
    else
        seg1[node]=seg1[node*2+1];
//    cout<<l<<" "<<r<<" "<<ind<<" "<<val<<" "<<sum<<" "<<seg1[node]<<endl;
}
void u2(int node,int l,int r,int ind,int val){
    if(ind<l||r<ind)R;
    if(l==r){
        seg2[node]=val;
        R;
    }
    u2(node*2,l,(l+r)/2,ind,val);
    u2(node*2+1,(l+r)/2+1,r,ind,val);
    if(seg2[node*2]==n&&seg2[node*2+1]==n){
        seg2[node]=n;
        R;
    }
    if(w[seg2[node*2]]>w[seg2[node*2+1]])
        seg2[node]=seg2[node*2];
    else
        seg2[node]=seg2[node*2+1];
}
int q1(int node,int l,int r,int st,int e){
    if(e<l||r<st)R n;
    if(st<=l&&r<=e){
        if(l==r)R seg1[node];
//        if(sum==7)
//            cout<<l<<" "<<r<<" "<<seg1[node]<<" "<<seg1[node*2]<<endl;
        if(seg1[node]==seg1[node*2])R q1(node*2,l,(l+r)/2,st,e);
        else R q1(node*2+1,(l+r)/2+1,r,st,e);
    }
    else{
        int i1=q1(node*2,l,(l+r)/2,st,e),i2=q1(node*2+1,(l+r)/2+1,r,st,e);
//        if(sum==7)
//            cout<<l<<" "<<r<<" "<<i1<<" "<<i2<<" "<<s[i1]<<" "<<s[i2]<<endl;
        if(s[i1]>s[i2])R i1;
        else R i2;
    }
}
int q2(int node,int l,int r,int st,int e){
    if(e<l||r<st)R n;
    if(st<=l&&r<=e){
        if(l==r){R seg2[node];}
//        cout<<l<<" "<<r<<"s"<<seg2[node]<<" "<<seg2[node*2]<<endl;
        if(seg2[node]==seg2[node*2])R q2(node*2,l,(l+r)/2,st,e);
        else R q2(node*2+1,(l+r)/2+1,r,st,e);
    }
    else{
        int i1=q2(node*2,l,(l+r)/2,st,e),i2=q2(node*2+1,(l+r)/2+1,r,st,e);
//        cout<<l<<" "<<r<<" "<<i1<<" "<<i2<<" "<<s[i1]<<" "<<s[i2]<<endl;
        if(w[i1]>w[i2])R i1;
        else R i2;
    }
}
multiset<int> m1,m2;
vector<int> vec1,vec2;
int bs1(int x){
    int ret=-1;
    int l=0,r=n;
    W(l<r){
        int mid=(l+r)/2;
        if(vec1[mid]<x){
            l=mid+1;
            ret=mid;
        }
        else r=mid;
    }
    R ret;
}
int bs2(int x){
    int ret=-1;
    int l=0,r=n;
    W(l<r){
        int mid=(l+r)/2;
        if(vec2[mid]<x){
            l=mid+1;
            ret=mid;
        }
        else r=mid;
    }
    R ret;
}
int putaway(int A_, int B_, int N, int X_[], int Y_[], int w_[], int s_[]) {
    A=A_,B=B_,n=N;
    for(int i=0;i<A;i++)
        X[i]=X_[i];
    for(int i=0;i<B;i++)
        Y[i]=Y_[i];
    for(int i=0;i<n;i++)
        w[i]=w_[i],s[i]=s_[i];
    for(int i=0;i<n;i++){
        v1.pb(i);
        v2.pb(i);
    }
    sort(all(v1),cmp1);
    sort(all(v2),cmp2);
    sort(X,X+A);
    sort(Y,Y+B);
    for(int i=0;i<n;i++){
        ind1[v1[i]]=i;
        ind2[v2[i]]=i;
        vec1.pb(w[i]);
        vec2.pb(s[i]);
    }
    sort(all(vec1));
    sort(all(vec2));
    for(int i=0;i<n;i++){
        u1(1,0,n-1,i,v1[i]);
        u2(1,0,n-1,i,v2[i]);
    }
    for(int i=0;i<A;i++)
        m1.insert(X[i]);
    for(int i=0;i<B;i++)
        m2.insert(Y[i]);
    int res=0;
    W(sum<n){
        vector<int> vec;
        if(m1.empty()&&m2.empty())R -1;
        if(!m1.empty()){
            int x;
            for(auto i : m1){
                x=bs1(i);
//                cout<<x<<endl;
                if(x==-1){
//                    cout<<'z';
                    vec.pb(i);
                    C;
                }
                x=q1(1,0,n-1,0,x);
//                cout<<x<<" ";
                if(x==n){
                    vec.pb(i);
//                    cout<<'z';
                }
                else{
                    u1(1,0,n-1,ind1[x],n);
                    if(B)u2(1,0,n-1,ind2[x],n);
                    sum++;
                }
            }
            for(auto i : vec){
                m1.erase(i);
            }
        }
//        cout<<'s';
        vec.clear();
        if(B&&!m2.empty()){
            int x;
            for(auto i : m2){
                x=bs2(i);
                if(x==-1){
//                    cout<<'r';
                    vec.pb(i);
                    C;
                }
                x=q2(1,0,n-1,0,x);
//                cout<<x<<" ";
                if(x==n){
                    vec.pb(i);
//                    cout<<'z';
                }
                else{
                    u1(1,0,n-1,ind1[x],n);
                    u2(1,0,n-1,ind2[x],n);
                    sum++;
                }
            }
            for(auto i : vec){
                m1.erase(i);
            }
        }
        for(auto i : vec)
            m2.erase(i);
        vec.clear();
        res++;
    }
    return res;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 53592 KB Output is correct
2 Correct 0 ms 53592 KB Output is correct
3 Correct 0 ms 53592 KB Output is correct
4 Correct 1683 ms 64344 KB Output is correct
5 Correct 1679 ms 64728 KB Output is correct
6 Correct 156 ms 57568 KB Output is correct
7 Incorrect 1696 ms 64728 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 53592 KB Output is correct
2 Correct 0 ms 53592 KB Output is correct
3 Correct 0 ms 53592 KB Output is correct
4 Correct 0 ms 53592 KB Output is correct
5 Correct 0 ms 53592 KB Output is correct
6 Correct 0 ms 53592 KB Output is correct
7 Correct 0 ms 53592 KB Output is correct
8 Correct 0 ms 53592 KB Output is correct
9 Correct 0 ms 53592 KB Output is correct
10 Correct 0 ms 53592 KB Output is correct
11 Correct 0 ms 53592 KB Output is correct
12 Correct 0 ms 53592 KB Output is correct
13 Correct 0 ms 53592 KB Output is correct
14 Correct 0 ms 53592 KB Output is correct
15 Correct 0 ms 53592 KB Output is correct
16 Correct 26 ms 53944 KB Output is correct
17 Correct 23 ms 53944 KB Output is correct
18 Correct 13 ms 53944 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 53592 KB Output is correct
2 Correct 0 ms 53592 KB Output is correct
3 Correct 0 ms 53592 KB Output is correct
4 Correct 0 ms 53592 KB Output is correct
5 Correct 0 ms 53592 KB Output is correct
6 Correct 0 ms 53592 KB Output is correct
7 Correct 0 ms 53592 KB Output is correct
8 Correct 0 ms 53592 KB Output is correct
9 Correct 0 ms 53592 KB Output is correct
10 Correct 1523 ms 64344 KB Output is correct
11 Correct 1883 ms 64728 KB Output is correct
12 Correct 156 ms 57568 KB Output is correct
13 Incorrect 1446 ms 64728 KB Output isn't correct
14 Halted 0 ms 0 KB -