Submission #402661

#	Time	Username	Problem	Language	Result	Execution time	Memory
402661		ACmachine	Robots (IOI13_robots)	C++17	90 / 100	677 ms	65540 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }


struct flow_edge{
    int src, dest;
    int flow, cap;
};
struct flow_network{
    vector<vector<int>> g;
    vector<flow_edge> edges;
    vector<int> level;
    vector<int> ptr;
    int s, t;
    int n, m = 0;
    flow_network(int _n, int _s, int _t) : n(_n), s(_s), t(_t){
        g.resize(n);
        level.resize(n);
        ptr.resize(n);
    }
    void add_edge(int src, int dest, int cap){
        edges.pb({src, dest, 0, cap});
        edges.pb({dest, src, 0, 0});
        g[src].pb(m);
        g[dest].pb(m + 1);
        m += 2;
    }
    bool bfs(){
        fill(all(level), -1);
        fill(all(ptr), 0);
        queue<int> q;
        q.push(s);
        level[s] = 0;
        while(!q.empty()){
            int v = q.front();
            q.pop();
            for(int id : g[v]){
                auto e = edges[id];
                if(e.cap - e.flow < 1) continue;
                if(level[e.dest] == -1){
                    level[e.dest] = level[e.src] + 1;
                    q.push(e.dest);
                }
            }
        }
        return level[t] != -1;
    }
    int dfs(int v, int pushed){
        if(pushed == 0)
            return 0;
        if(v == t) return pushed;
        for(int &cid = ptr[v]; cid < g[v].size(); ++cid){
            int id = g[v][cid];
            auto &e = edges[id];
            auto &e2 = edges[id^1];
            if(e.cap - e.flow < 1 || level[e.dest] != level[e.src] + 1) continue;
            int tr = dfs(e.dest, min(pushed, e.cap - e.flow));
            if(tr == 0) continue;
            e.flow += tr; e2.flow -= tr;
            return tr;
        }
        return 0;
    }
    int get_flow(){
        int res_flow = 0;
        while(true){
            if(!bfs())
                break;
            while(int pushed = dfs(s, INF))
                res_flow += pushed;
        }
        return res_flow;
    }
};
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
    auto solve_small = [&](){
        multiset<int> se;
        REP(i, T) se.insert(W[i]);
        vector<int> nx;
        REP(i, A) nx.pb(X[i]);
        if(*se.rbegin() >= *max_element(all(nx)))
            return -1;
        int ans = 0;
        int pp = 0;
        sort(all(nx));
        while(!se.empty()){
            ans++;
            int nxt_pp = pp;
            FOR(i, pp, nx.size(), 1){
                auto it = se.lower_bound(nx[i]);
                if(it == se.begin()){
                    nxt_pp = max(nxt_pp, i + 1);
                }
                else{
                    it--; se.erase(it);
                }
            }
            pp = nxt_pp;
        }
        return ans;
    };
    if(B == 0)
        return solve_small();
    auto construct_network = [&](){
        flow_network preset(T + 2 * A + 2 * B + 2, T + 2 * A + 2 * B, T + 2 * A + 2 * B + 1);
        // [0 ... A) - Acka; [A ... A + B) - bcka
        // [A + B ... A + B + T) - hracky
        // potom specialne vrcholy, na limit E
        vector<int> nx;
        REP(i, A) nx.pb(X[i]);
        sort(all(nx));
        nx.erase(unique(all(nx)), nx.end());
        vector<int> toys_sorted(T);
        iota(all(toys_sorted), 0);
        sort(all(toys_sorted), [&](int lhs, int rhs){
            return W[lhs] < W[rhs];
        });
        int pp = 0;
        int curr = A + B + T;
        REP(i, nx.size()){
            while(pp < T && W[toys_sorted[pp]] < nx[i]){
                preset.add_edge(curr, A + B + toys_sorted[pp], 1);
                pp++;
            }
            REP(j, A){
                if(X[j] >= nx[i]){
                    preset.add_edge(j, curr, INF);
                }
            }
            curr++;
        }
        vector<int> ny;
        REP(i, B) ny.pb(Y[i]);
        sort(all(ny));
        ny.erase(unique(all(ny)), ny.end());
        sort(all(toys_sorted), [&](int lhs, int rhs){
            return S[lhs] < S[rhs];
        });
        pp = 0;
        REP(i, ny.size()){
            while(pp < T && S[toys_sorted[pp]] < ny[i]){
                preset.add_edge(curr, A + B + toys_sorted[pp], 1);
                pp++;
            }
            REP(j, B){
                if(Y[j] >= ny[i]){
                    preset.add_edge(A + j, curr, INF);
                }
            }
            curr++;
        }
        REP(i, T){
            preset.add_edge(A + B + i, preset.t, 1);
        }
        return preset;
    };
    int l = 0;
    int r = 1000005;
    int ans = INF;
    while(l <= r){
        int mid = (l + r) >> 1;
        flow_network fn = construct_network();
        REP(i, A + B){
            fn.add_edge(fn.s, i, mid);
        }
        int flow = fn.get_flow();
        if(flow == T){
            ans = mid;
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    if(ans == INF)
        return -1;
    return ans;
}

Compilation message (stderr)

robots.cpp: In constructor 'flow_network::flow_network(int, int, int)':
robots.cpp:69:9: warning: 'flow_network::n' will be initialized after [-Wreorder]
   69 |     int n, m = 0;
      |         ^
robots.cpp:68:9: warning:   'int flow_network::s' [-Wreorder]
   68 |     int s, t;
      |         ^
robots.cpp:70:5: warning:   when initialized here [-Wreorder]
   70 |     flow_network(int _n, int _s, int _t) : n(_n), s(_s), t(_t){
      |     ^~~~~~~~~~~~
robots.cpp: In member function 'int flow_network::dfs(int, int)':
robots.cpp:106:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for(int &cid = ptr[v]; cid < g[v].size(); ++cid){
      |                                ~~~~^~~~~~~~~~~~~
robots.cpp: In lambda function:
robots.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
robots.cpp:143:13: note: in expansion of macro 'FOR'
  143 |             FOR(i, pp, nx.size(), 1){
      |             ^~~
robots.cpp: In lambda function:
robots.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
robots.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
robots.cpp:174:9: note: in expansion of macro 'REP'
  174 |         REP(i, nx.size()){
      |         ^~~
robots.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
robots.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
robots.cpp:194:9: note: in expansion of macro 'REP'
  194 |         REP(i, ny.size()){
      |         ^~~

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