Submission #623597

#	Time	Username	Problem	Language	Result	Execution time	Memory
623597		ACGN	Fountain Parks (IOI21_parks)	C++17	5 / 100	248 ms	19792 KiB

parks

#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define vi vector<int>
#define pii pair<int,int>
#define vii vector<pii>
#define pb push_back
#include "parks.h"

struct dsu {
    int D[3][2];
    dsu() {
        D[0][0] = 0;
        D[0][1] = 0;
        D[1][0] = 0;
        D[1][1] = 0;
        D[2][0] = 0;
        D[2][1] = 0;
    }
    void join(int x1,int x2,int y1,int y2) {
        x1 = x1 / 2 - 1;x2 = x2 / 2 - 1;
        y1 /= 2;y2 /= 2;
        int m = min(D[x1][y1], D[x2][y2]);
        int M = min(D[x1][y1], D[x2][y2]);
        for (int i = 0;i < 3;i++) {
            for (int j = 0;j < 2;j++) {
                if (D[i][j] == M) D[i][j] = m;
            }
        }
    }
    bool conn() {
        return !(D[0][0] | D[0][1] | D[1][0] | D[1][1] | D[2][0] | D[2][1]);
    }
};

struct eg {
    int x1;int y1;
    int x2;int y2;
    int b1;int b2;
    eg(int a, int b, int c, int d) {
        x1 = a;y1 = b;x2 = c;y2 = d;b1 = -1;b2 = 1;
    }
    eg(int a1, int a2, int x3, int x4, int x5, int x6) {
        x1 = a1;y1 = a2;x2 = x3;y2 = x4;b1 = x5;b2 = x6;
    }
    void out() {
    }
};
eg add(eg v, int y) {
    //cout << "adding " << y << endl;
    v.y1 += y;v.y2 += y;v.b2 += y;
    return v;
}

bool abmissible(eg e, int x) {
    return (max(abs(x - e.x1), abs(x - e.x2))) == 1;
}

vector<eg> transition(int bm1, int bm2, int twoban) {
    vector<eg> v;
    if ((bm1 == 2) && (bm2 == 7)) {
        v.pb(eg(4, 0, 4, 2, 5, 1));
        v.pb(eg(2, 2, 4, 2, 3, 1));
        v.pb(eg(4, 2, 6, 2, 5, 3));
        return v;
    }
    if ((bm1 & bm2) == 0) return v;
    if (bm1 & bm2 & 1) v.pb(eg(2, 0, 2, 2));
    if (bm1 & bm2 & 2) v.pb(eg(4, 0, 4, 2));
    if (bm1 & bm2 & 4) v.pb(eg(6, 0, 6, 2));
    if ((bm2 & 3) == 3) v.pb(eg(2, 2, 4, 2));
    if ((bm2 & 6) == 6) v.pb(eg(4, 2, 6, 2));
    int vc = 0;
    if (bm2 & 1) vc++;
    if (bm2 & 2) vc++;
    if (bm2 & 4) vc++;
    for (auto i:v) i.out();

    for (int i = 0;i < (1 << v.size());i++) {
        int vk = (!!(i & 1)) + (!!(i & 2)) + (!!(i & 4)) + (!!(i & 8)) + (!!(i & 16));
        if (vk != vc) continue;
        vector<eg> sim;
        for (int j = 0;j < v.size();j++) {
            if (i & (1 << j)) sim.pb(v[j]);
        }
        dsu d;
        for (auto e : sim) {
            d.join(e.x1, e.x2, e.y1, e.y2);
        }
        if (!d.conn()) continue;
        for (int j = 0;j < 64;j++) {
            int c1 = j % 4, c2 = (j % 16) / 4, c3 = j / 16;
            if (c1 == c2) continue;
            if (c1 == c3) continue;
            if (c3 == c2) continue;
            if (twoban) {
                if ((c1 == 2) || (c2 == 2) || (c3 == 2)) continue;
            }
            c1 = c1 * 2 + 1;
            c2 = c2 * 2 + 1;
            c3 = c3 * 2 + 1;
            if (!abmissible(sim[0], c1)) continue;
            if (vk > 1) { if (!abmissible(sim[1], c2)) continue; }
            if (vk > 2) { if (!abmissible(sim[2], c3)) continue; }
            sim[0].b1 = c1;if (vk == 1) return sim;
            sim[1].b1 = c2;if (vk == 2) return sim;
            sim[2].b1 = c3;
            return sim;
        }
    }
    return vector<eg>();
}

int construct_roads(std::vector<int> x, std::vector<int> y) {
    int m = 1e9, M = -1e9;
    for (auto i : y) m = min(i, m);
    for (auto i : y) M = max(i, M);
    vi stk((M - m + 2) / 2);
    for (int i = 0;i < x.size();i++) {
        stk[(y[i] - m) / 2] |= (1 << (x[i] / 2 - 1));
    }
    for (auto i : stk) {
        if (!i) return 0;
    }

    vector<eg> vek;
    if (stk[0] == 5) {
        int ext = 0;
        for (int i = 0;i < stk.size();i++) {
            if (stk[i] == 7) {
                for (int j = 0;j < i;j++) {
                    vek.push_back(eg(2, m + 2 * j, 2, m + 2 * j + 2, 1, m + 2 * j + 1));
                    vek.push_back(eg(6, m + 2 * j, 6, m + 2 * j + 2, 7, m + 2 * j + 1));
                }
                m += 2 * i;
                vi st2;
                ext = 1;
                for (int j = i;j < stk.size();j++) st2.push_back(stk[j]);
                st2 = stk;
                continue;
            }
            else if (stk[i] != 5) return 0;
        }
        if (!ext) return 0;
    }
    int past = 0;
    for (int i = 0;i < stk.size() - 1;i++) {
        vector<eg> v2 = transition(stk[i], stk[i + 1], past);
        if ((stk[i] == 2) && (stk[i + 1] == 7)) past = 1;
        if (v2.empty()) return 0;
        for (auto k : v2) {
            vek.pb(add(k, i * 2 + m));
        }
    }
    map<pii, int> mpi;
    for (int i = 0;i < x.size();i++) {
        mpi[pii(x[i], y[i])] = i;
    }
    vi u, v, a, b;
    for (auto i : vek) {
        i.out();
        int u1 = mpi[pii(i.x1, i.y1)];
        int v1 = mpi[pii(i.x2, i.y2)];
        u.pb(u1);v.pb(v1);
        a.pb(i.b1);b.pb(i.b2);
    }
    build(u, v, a, b);
    return 1;
}

Compilation message (stderr)

parks.cpp: In function 'std::vector<eg> transition(int, int, int)':
parks.cpp:83:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<eg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for (int j = 0;j < v.size();j++) {
      |                        ~~^~~~~~~~~~
parks.cpp: In function 'int construct_roads(std::vector<int>, std::vector<int>)':
parks.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for (int i = 0;i < x.size();i++) {
      |                    ~~^~~~~~~~~~
parks.cpp:129:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  129 |         for (int i = 0;i < stk.size();i++) {
      |                        ~~^~~~~~~~~~~~
parks.cpp:138:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  138 |                 for (int j = i;j < stk.size();j++) st2.push_back(stk[j]);
      |                                ~~^~~~~~~~~~~~
parks.cpp:147:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |     for (int i = 0;i < stk.size() - 1;i++) {
      |                    ~~^~~~~~~~~~~~~~~~
parks.cpp:156:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  156 |     for (int i = 0;i < x.size();i++) {
      |                    ~~^~~~~~~~~~

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