Submission #1070405

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070405		Arapak	Fountain Parks (IOI21_parks)	C++17	0 / 100	1 ms	348 KiB

parks

#include "parks.h"
#include "bits/stdc++.h"
using namespace std;

#define rep(i,a,b) for(int i=(a);i<(b);++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

#ifdef DEBUG
auto& operator<<(auto &os, const pair<auto,auto> &p) {
    return os<<"("<<p.first<<", "<<p.second<<")";
}
auto& operator<<(auto &os, const auto &v) {
    os<<"{";
    for(auto it=begin(v);it!=end(v);++it) {
        if(it != begin(v)) os<<", ";
        os<<(*it);
    }
    return os<<"}";
}

void dbg_out(auto... x) {
    ((cerr<<' '<<x), ...) << endl;
}
#define dbg(x...) cerr<<"("<<#x<<"):", dbg_out(x);
#else
#define dbg(...)
#endif

struct Fountain {
    int x, y, index;

    friend bool operator<(const Fountain &a, const Fountain &b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    }
};

struct Bench {
    int a, b;
    int x, y;

    friend bool operator<(const Bench &a, const Bench &b) {
        return tie(a.x, a.y) < tie(b.x, b.y);
    }
};

void build_from_benches(set<Bench> &benches) {
    vi u, v, a, b;
    for(auto bench : benches) {
        u.push_back(bench.a);
        v.push_back(bench.b);
        a.push_back(bench.x);
        b.push_back(bench.y);
    }
    build(u, v, a, b);
}

int construct_roads(vi x, vi y) {
    int n = sz(x);
    dbg(x, y);
    set<Fountain> s;
    rep(i,0,n) s.insert({x[i], y[i], i});
    set<Bench> benches;
    for(auto f : s) {
        {
            auto it = s.find({f.x - 2, f.y, -1});
            if(it != s.end()) {
                auto t = *it;
                Bench b;
                b.a = f.index;
                b.b = t.index;
                b.x = f.x - 1;

                b.y = f.y - 1;
                if(benches.count(b))
                    b.y = f.y + 1;
                if(benches.count(b))
                    return 0;
                benches.insert(b);
            }
        }

        {
            auto it = s.find({f.x, f.y - 2, -1});
            if(it != s.end()) {
                auto t = *it;
                Bench b;
                b.a = f.index;
                b.b = t.index;
                b.y = f.y - 1;

                b.x = f.x - 1;
                if(benches.count(b))
                    b.x = f.x + 1;
                if(benches.count(b))
                    return 0;
                benches.insert(b);
            }
        }
    }
    build_from_benches(benches);
    return 1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 15
• Subtask 4: 0 / 20
• Subtask 5: 0 / 20
• Subtask 6: 0 / 30