제출 #1101448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1101448		alexander707070	로봇 (IOI13_robots)	C++14	39 / 100	152 ms	65536 KiB

robots

#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]<=s[k].y)return -1;
    if(x[n]<=t[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;
}*/

컴파일 시 표준 에러 (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++){
      |                 ~^~~~~~~~~~~~

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