oj.uz

Submission #65355

# Submission time Handle Problem Language Result Execution time Memory
65355 2018-08-07T12:32:31 Z edisonhello Robots (IOI13_robots) C++14
100 / 100
 2411 ms 38592 KB 
#include "robots.h"
#include<bits/stdc++.h>

using namespace std;

/* struct edge{
    int u,v,f;
};
vector<edge> edg;
vector<int> G[11115];

void ae(int u,int v,int f){
    // cout<<"addedge: "<<u<<" "<<v<<" "<<f<<endl;
    G[u].push_back(edg.size());
    edg.push_back({u,v,f});
    G[v].push_back(edg.size());
    edg.push_back({v,u,0});
}

int idx[11115],vis[11115],dep[11115];

bool bfs(int s,int t,int z){
    vis[s]=z; dep[s]=1;
    queue<int> q; q.push(s);
    while(q.size()){
        int now=q.front(); q.pop();
        for(int eid:G[now]){
            edge &e=edg[eid];
            if(vis[e.v]!=z && e.f>0){
                q.push(e.v);
                vis[e.v]=z;
                dep[e.v]=dep[now]+1;
            }
        }
    }
    // cout<<"finish bfs"<<endl;
    return (vis[t]==z);
}

int dfs(int now,int fl,int dis){
    if(now==dis)return fl;
    if(!fl)return 0;
    int rt=0;
    for(int &i=idx[now];i<G[now].size();++i){
        int eid=G[now][i];
        edge &e=edg[eid];
        if(dep[e.v]==dep[now]+1 && e.f>0){
            int f=dfs(e.v,min(fl,e.f),dis);
            rt+=f; fl-=f;
            e.f-=f;
            edg[eid^1].f+=f;
            if(!fl)return rt;
        }
    }
    return rt;
}

int flow(int s,int t){
    int vis_ptr=0,ans=0;
    while(bfs(s,t,++vis_ptr)){
        memset(idx,0,sizeof(idx));
        ans+=dfs(s,1e9,t);
    }
    return ans;
} */

int putaway(int a, int b, int t, int x[], int y[], int w[], int s[]) {
    // cout<<"in: putaway"<<endl;
    if([&]()->bool{
        int xmx=0,ymx=0;
        for(int i=0;i<a;++i)xmx=max(xmx,x[i]);
        for(int i=0;i<b;++i)ymx=max(ymx,y[i]);
        for(int i=0;i<t;++i)if(w[i]>=xmx && s[i]>=ymx)return 1;
        return 0;
    }())return -1;
    vector<pair<int,int>> pz(t);
    for(int i=0;i<t;++i)pz[i].first=w[i],pz[i].second=s[i];
    sort(pz.begin(),pz.end());
    sort(x,x+a);
    sort(y,y+b);
    int L=1,R=t;
    while(R>L){
        // cout<<"BS range "<<L<<" to "<<R<<endl;
        int M=(L+R)>>1;
        if([&](int T)->bool{
            priority_queue<int,vector<int>,less<int>> pq;
            int pzt=0;
            for(int i=0;i<a;++i){
                // cout<<"i: "<<i<<endl;
                while(pzt<t && pz[pzt].first<x[i])pq.push(pz[pzt++].second);
                for(int z=0;z<T;++z)if(pq.size())pq.pop(); else break;
            }
            while(pzt<t)pq.push(pz[pzt++].second);
            for(int i=b-1;i>=0;--i){
                // cout<<"i: "<<i<<endl;
                if(pq.size() && pq.top()>=y[i])return 0;
                for(int z=0;z<T;++z)if(pq.size())pq.pop(); else break;
            }
            return pq.empty();
        }(M))R=M;
        else L=M+1;
    }
    return L;
}

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 552 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 1830 ms 12264 KB Output is correct
5 Correct 223 ms 12264 KB Output is correct
6 Correct 52 ms 12264 KB Output is correct
7 Correct 490 ms 12264 KB Output is correct
8 Correct 1165 ms 12264 KB Output is correct
9 Correct 2347 ms 12852 KB Output is correct

Subtask #3
25.0 / 25.0

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

Subtask #4
37.0 / 37.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 12852 KB Output is correct
2 Correct 3 ms 12852 KB Output is correct
3 Correct 2 ms 12852 KB Output is correct
4 Correct 3 ms 12852 KB Output is correct
5 Correct 3 ms 12852 KB Output is correct
6 Correct 2 ms 12852 KB Output is correct
7 Correct 3 ms 12852 KB Output is correct
8 Correct 3 ms 12852 KB Output is correct
9 Correct 2 ms 12852 KB Output is correct
10 Correct 1642 ms 12852 KB Output is correct
11 Correct 212 ms 12852 KB Output is correct
12 Correct 47 ms 12852 KB Output is correct
13 Correct 473 ms 12852 KB Output is correct
14 Correct 1064 ms 12852 KB Output is correct
15 Correct 2 ms 12852 KB Output is correct
16 Correct 3 ms 12852 KB Output is correct
17 Correct 3 ms 12852 KB Output is correct
18 Correct 3 ms 12852 KB Output is correct
19 Correct 2 ms 12852 KB Output is correct
20 Correct 3 ms 12852 KB Output is correct
21 Correct 16 ms 12852 KB Output is correct
22 Correct 2286 ms 14276 KB Output is correct
23 Correct 2370 ms 15932 KB Output is correct
24 Correct 674 ms 15932 KB Output is correct
25 Correct 636 ms 15932 KB Output is correct
26 Correct 879 ms 15932 KB Output is correct
27 Correct 829 ms 15932 KB Output is correct
28 Correct 1113 ms 25488 KB Output is correct
29 Correct 2411 ms 38592 KB Output is correct