oj.uz

Submission #623593

# Submission time Handle Problem Language Result Execution time Memory
623593 2022-08-06T03:51:02 Z ACGN Fountain Parks (IOI21_parks) C++17
5 / 100
 216 ms 19900 KB 
#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 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]);
        }
        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;
    }
    cout << endl;
    vector<eg> vek;
    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

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 113 ms 15984 KB Output is correct
10 Correct 9 ms 1864 KB Output is correct
11 Correct 54 ms 8744 KB Output is correct
12 Correct 17 ms 2612 KB Output is correct
13 Correct 10 ms 1204 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 123 ms 15960 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 113 ms 15984 KB Output is correct
10 Correct 9 ms 1864 KB Output is correct
11 Correct 54 ms 8744 KB Output is correct
12 Correct 17 ms 2612 KB Output is correct
13 Correct 10 ms 1204 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 123 ms 15960 KB Output is correct
17 Incorrect 1 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 113 ms 15984 KB Output is correct
10 Correct 9 ms 1864 KB Output is correct
11 Correct 54 ms 8744 KB Output is correct
12 Correct 17 ms 2612 KB Output is correct
13 Correct 10 ms 1204 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 123 ms 15960 KB Output is correct
17 Incorrect 1 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 113 ms 15984 KB Output is correct
10 Correct 9 ms 1864 KB Output is correct
11 Correct 54 ms 8744 KB Output is correct
12 Correct 17 ms 2612 KB Output is correct
13 Correct 10 ms 1204 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 123 ms 15960 KB Output is correct
17 Runtime error 1 ms 340 KB Execution killed with signal 11
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 113 ms 15984 KB Output is correct
10 Correct 9 ms 1864 KB Output is correct
11 Correct 54 ms 8744 KB Output is correct
12 Correct 17 ms 2612 KB Output is correct
13 Correct 10 ms 1204 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 123 ms 15960 KB Output is correct
17 Incorrect 216 ms 19900 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 300 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 113 ms 15984 KB Output is correct
10 Correct 9 ms 1864 KB Output is correct
11 Correct 54 ms 8744 KB Output is correct
12 Correct 17 ms 2612 KB Output is correct
13 Correct 10 ms 1204 KB Output is correct
14 Correct 1 ms 340 KB Output is correct
15 Correct 2 ms 564 KB Output is correct
16 Correct 123 ms 15960 KB Output is correct
17 Incorrect 1 ms 212 KB Given structure is not connected: There is no path between vertices 0 and 1
18 Halted 0 ms 0 KB -