Submission #1101434

#TimeUsernameProblemLanguageResultExecution timeMemory
1101434alexander707070Robots (IOI13_robots)C++14
0 / 100
82 ms13160 KiB
#include<bits/stdc++.h> #include "robots.h" #define MAXN 30007 using namespace std; struct edge{ int to; bool cap; int rev; }; struct toy{ int x,y,id; }; int n,m,k; int x[MAXN],y[MAXN]; toy s[MAXN],t[MAXN]; bool cmp(toy fr,toy sc){ return fr.x<sc.x; } bool cmp2(toy fr,toy sc){ return fr.y<sc.y; } vector<edge> g[MAXN]; void add_edge(int from,int to){ g[from].push_back({to,1,int(g[to].size())}); g[to].push_back({from,0,int(g[from].size())-1}); } int source,sink,flow,maxflow; int li[MAXN],tim; int dfs(int x){ if(x==sink)return 1; li[x]=tim; for(int i=0;i<g[x].size();i++){ if(li[g[x][i].to]==tim or !g[x][i].cap)continue; int curr=dfs(g[x][i].to); if(curr>0){ g[x][i].cap=false; g[g[x][i].to][g[x][i].rev].cap=true; return 1; } } return 0; } int cnt[MAXN],cnt2[MAXN]; bool is[MAXN]; bool greedy(int days){ for(int i=1;i<=10;i++){ for(int i=1;i<=n;i++)cnt[i]=days; for(int f=1;f<=m;f++)cnt2[i]=days; random_shuffle(t+1,t+k+1); for(int f=1;f<=k;f++)is[f]=false; for(int f=1;f<=k;f++){ for(int d=1;d<=n;d++){ if(x[d]>t[f].x and cnt[d]>0){ cnt[d]--; is[f]=true; break; } } } for(int f=1;f<=k;f++){ if(is[f])continue; for(int d=1;d<=m;d++){ if(y[d]>t[f].y and cnt2[d]>0){ cnt2[d]--; is[f]=true; break; } } } for(int f=1;f<=k;f++){ if(!is[f])break; if(f==k)return true; } } return false; } bool check(int days){ if(greedy(days))return true; sort(t+1,t+k+1,cmp2); int A=min(n*days,k); int B=min(m*days,k); source=0; sink=A+B+k+1; for(int i=0;i<=sink;i++)g[i].clear(); for(int i=1;i<=A+B;i++)add_edge(source,i); for(int i=1;i<=k;i++)add_edge(A+B+i,sink); int pt=0; for(int i=n;i>=1;i--){ for(int z=1;z<=days;z++){ pt++; if(pt>k)break; for(int f=1;f<=k-pt+1;f++){ if(x[i]<=s[f].x)continue; add_edge(pt,A+B+s[f].id); } } } pt=0; for(int i=m;i>=1;i--){ for(int z=1;z<=days;z++){ pt++; if(pt>k)break; for(int f=1;f<=k-pt+1;f++){ if(y[i]<=t[f].y)continue; add_edge(A+pt,A+B+t[f].id); } } } maxflow=0; while(true){ tim++; flow=dfs(source); if(flow==0)break; maxflow+=flow; } return maxflow==k; } int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) { //int putaway(int A, int B, int T, vector<int> X, vector<int> Y, vector<int> W, vector<int> S) { n=A; m=B; k=T; for(int i=1;i<=n;i++)x[i]=X[i-1]; for(int i=1;i<=m;i++)y[i]=Y[i-1]; for(int i=1;i<=k;i++)s[i]=t[i]={W[i-1],S[i-1],i}; sort(x+1,x+n+1); sort(y+1,y+m+1); sort(s+1,s+k+1,cmp); sort(t+1,t+k+1,cmp2); if(x[n]<=s[k].x and y[m]<=t[k].y)return -1; int l=0,r=k+1,tt; while(l+1<r){ tt=(l+r)/2; if(check(tt))r=tt; else l=tt; } return r; } /*int main(){ cout<<putaway(3,2,10,{6,2,9},{4,7},{4,8,2,7,1,5,3,8,7,10},{6,5,3,9,8,1,3,7,6,5})<<"\n"; return 0; }*/

Compilation message (stderr)

robots.cpp: In function 'int dfs(int)':
robots.cpp:43:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0;i<g[x].size();i++){
      |                 ~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...