Submission #28007

#	Time	Username	Problem	Language	Result	Execution time	Memory
28007		repeating	Robots (IOI13_robots)	C++11	39 / 100	3000 ms	58884 KiB

robots

#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;
    int mx1=0,mx2=0;
    for(int i=0;i<A;i++)
        X[i]=X_[i],mx1=max(mx1,X[i]);
    for(int i=0;i<B;i++)
        Y[i]=Y_[i],mx2=max(mx2,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);
    }
    for(int i=0;i<n;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){
        if(m1.empty()&&m2.empty())R -1;
        vector<int> vec;
        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 / 14
• Subtask 2: 0 / 14
• Subtask 3: 25 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10