Submission #222911

#	Time	Username	Problem	Language	Result	Execution time	Memory
222911		laoriu	Robots (IOI13_robots)	C++14	100 / 100	503 ms	26212 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"

using namespace std;
typedef pair <int,int> pp;
pp A[1000002];
int pos[1000002],nextt[100002],C[100002];
int dsu[100002],val[100002];
int root(int u)
{
    int v=u;
    while (dsu[u]>=0) u=dsu[u];
    while (dsu[v]>=0)
    {
        int p=dsu[v];
        dsu[v]=u;
        v=p;
    }
    return u;
}
int unionn(int u,int v)
{
    if (dsu[u]>dsu[v]) swap(u,v);
    dsu[u]+=dsu[v];dsu[v]=u;
    val[u]=max(val[u],val[v]);
}
int check(int a,int b,int n,int X[],int Y[],int k)
{
    for (int i=0;i<=b;i++)
    {
        C[i]=0;
        dsu[i]=-1;val[i]=i;
       // assert(root(val[i])==i);
    }
    vector <int> P;
    //cout<<"cac "<<k<<endl;
    for (int i=n-1;i>=0;i--)
    {
        int p=pos[i];
        p=root(p);
        if (val[p]==b) P.push_back(A[i].first);
        else
        {
            int x=val[p];
            assert(C[x]<k);
            //if (C[x]>=k) cerr<<p<<' '<<x<<endl;
            C[x]++;
            if (C[x]==k)
            {
                unionn(p,root(x+1));
                int u=root(p);
                assert(val[u]>=x+1);
               // assert(root(x)==root(x+1));
            }
        }
    }
    for (int i=0;i<P.size();i+=k)
        if (i/k>=a||P[i]>X[i/k]) return 0;
    return 1;
}
int putaway(int a,int b,int n,int X[],int Y[],int W[],int S[])
{
    sort(X,X+a,greater<int>());sort(Y,Y+b);

    for (int i=0;i<n;i++)
    {
        W[i]++;S[i]++;
        A[i].first=W[i];
        A[i].second=S[i];
    }
    sort(A,A+n);
    for (int i=0;i<n;i++)
    {
        int d=0;int c=b-1;
        pos[i]=b;
        while (d<=c)
        {
            int mid=(d+c)/2;
            if (Y[mid]>=A[i].second) {pos[i]=mid;c=mid-1;}
            else d=mid+1;
        }
       // cout<<A[i].first<<' '<<A[i].second<<' '<<pos[i]<<endl;
    }
    int d=1;int c=n;int res=-1;
    while (d<=c)
    {
        int mid=(d+c)/2;
        if (check(a,b,n,X,Y,mid)) {res=mid;c=mid-1;}
        else d=mid+1;
    }
    return res;
}
/*int main()
{
    freopen("robotz.inp","r",stdin);
    freopen("robotz.out","w",stdout);
    int a,b,n,X[50002],Y[50002],W[1000002],S[1000002];
    cin>>a>>b>>n;
    for (int i=0;i<a;i++) cin>>X[i];
    for (int i=0;i<b;i++) cin>>Y[i];
    for (int i=0;i<n;i++) cin>>W[i]*/

Compilation message (stderr)

robots.cpp: In function 'int unionn(int, int)':
robots.cpp:26:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^
robots.cpp: In function 'int check(int, int, int, int*, int*, int)':
robots.cpp:57:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<P.size();i+=k)
                  ~^~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 37 / 37
• Subtask 5: 10 / 10