oj.uz

Submission #572817

# Submission time Handle Problem Language Result Execution time Memory
572817 2022-06-05T10:33:17 Z baluteshih Mars (APIO22_mars) C++17
21 / 100
 43 ms 2924 KB 
#include "mars.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define SZ(a) ((int)a.size())
#define ALL(v) v.begin(), v.end()
#define pb push_back

char mp[100][100];
pii boss[100][100];
pii mapping[100000];

pii finds(pii a) {
    if (a == pii(-1, -1)) return pii(-1, -1);
    if (a == boss[a.X][a.Y]) return a;
    return boss[a.X][a.Y] = finds(boss[a.X][a.Y]);
}

int Union(pii a, pii b) {
    a = finds(a), b = finds(b);
    if (a == b)
        return 0;
    if (a > b)
        swap(a, b);
    //cerr << "Union " << a.X << " " << a.Y << " " << b.X << " " << b.Y << "\n";
    boss[b.X][b.Y] = a;
    return 1;
}

string process(vector<vector<string>> a, int i, int j, int k, int n) {
    const int ANS = __lg(((2 * n + 1) * (2 * n + 1) + 1) / 2) + 2;
    const int SZ = 4; 

    auto decode = [&](string s) {
        int rt = 0;
        for (int t = 0; t < SZ(s); ++t)
            if (s[t] == '1')
                rt |= 1 << t;
        return rt;
    };

    auto encode = [](int x, int len) {
        string rt(len, '0');
        for (int t = 0; t < len; ++t)
            if (x >> t & 1)
                rt[t] = '1', x -= 1 << t;
        assert(x == 0);
        return rt;
    };

    int m = 2 * (n - k - 1);
    int num = 2 * n - (m + 2) + 2 * n - (m + 2);
    int nxt = 2 * n - (m) + 2 * n - (m);

    auto place = [&](int p, int q, int tm) {
        if (q == tm + 2)
            return 2 * n - p;
        return 2 * n - (tm + 3) + p - (tm + 2);
    };

    auto coord = [&](int x, int tm) {
        if (x <= 2 * n - (tm + 3))
            return pii(2 * n - x, tm + 2);
        x -= 2 * n - (tm + 3);
        return pii(tm + 2, x + tm + 2);
    };

    auto check = [&](int x, int y) {
        if (x < m || x >= 2 * n + 1) return 0;
        if (y < m || y >= 2 * n + 1) return 0;
        if (x > m + 2 && y > m + 2) return 0;
        if (boss[x][y].X == -1) return 0;
        return 1;
    };

    if (i == m && j == m) {

        if (k == 0 && a[2][2][0] == '1') {
            a[2][2][100 - ANS] = '1';
            a[2][2][1] = '1';
        }

        int sum = decode(a[2][2].substr(100 - ANS, ANS));
        //cerr << "prv sum = " << sum << "\n";
        for (int p = m; p < m + 3; ++p)
            for (int q = m; q < m + 3; ++q) {
                mp[p][q] = a[p - m][q - m][0];
                boss[p][q] = pii(p, q);
                if (mp[p][q] == '1')
                    sum += (p != m + 2 || q != m + 2);
                else
                    boss[p][q] = pii(-1, -1);
            }
        for (int p = m; p < m + 2; ++p)
            for (int q = m + 3; q < 2 * n + 1; ++q) {
                mp[p][q] = a[p - m][2][q - m - 2];
                mp[q][p] = a[2][p - m][q - m - 2];
                boss[p][q] = pii(p, q);
                if (mp[p][q] == '1')
                    ++sum;
                else
                    boss[p][q] = pii(-1, -1);
                boss[q][p] = pii(q, p);
                if (mp[q][p] == '1')
                    ++sum;
                else
                    boss[q][p] = pii(-1, -1);
            }
        //cerr << "sum = " << sum << "\n";
        for (int p = 0; p < num; ++p)
            mapping[p] = pii(2 * n + 1, 2 * n + 1);
        mapping[0] = pii(-1, -1);
        for (int p = 0, nw = 1; p < num; ++p, nw += SZ) {
            int d = decode(a[2][2].substr(nw, SZ));
            pii c = coord(p, m);
            mapping[d] = min(mapping[d], c);
        }
        for (int p = 0, nw = 1; p < num; ++p, nw += SZ) {
            int d = decode(a[2][2].substr(nw, SZ));
            pii c = coord(p, m);
            //cerr << c.X << " " << c.Y << " code = " << d << ", mapping = " << mapping[d].X << " " << mapping[d].Y << "\n";
            boss[c.X][c.Y] = mapping[d];
        }
        /*for (int p = m; p < 2 * n + 1; ++p)
            for (int q = m; q < 2 * n + 1; ++q)
                if (check(p, q)) {
                    cerr << "boss " << p << " " << q << " = " << boss[p][q].X << " " << boss[p][q].Y << "\n";
                }*/
        if (check(m + 2, m + 2)) {
            if (check(m + 3, m + 2))
                Union(pii(m + 2, m + 2), pii(m + 3, m + 2));
            if (check(m + 2, m + 3))
                Union(pii(m + 2, m + 2), pii(m + 2, m + 3));
        }
        for (int p = m; p < 2 * n + 1; ++p)
            for (int q = m; q < 2 * n + 1; ++q)
                if (check(p, q)) {
                    if (check(p + 1, q))
                        sum -= Union(pii(p, q), pii(p + 1, q));
                    if (check(p, q + 1))
                        sum -= Union(pii(p, q), pii(p, q + 1));
                }
        if (k == n - 1)
            return encode(sum, ANS) + string(100 - ANS, '0');
        string rt(1, a[0][0][0]);

        vector<pii> ele(1, pii(-1, -1));
        for (int p = 0; p < nxt; ++p) {
            pii c = coord(p, m - 2);
            ele.pb(finds(c));
        }
        sort(ALL(ele)), ele.resize(unique(ALL(ele)) - ele.begin());
        for (int p = 0; p < nxt; ++p) {
            pii c = coord(p, m - 2);
            rt += encode(lower_bound(ALL(ele), finds(c)) - ele.begin(), SZ);
        }

        rt.resize(100 - ANS, '0');
        return rt + encode(sum, ANS);
    }
    if (i == m) {
        a[2][0].pop_back(), a[2][0].pop_back();
        a[2][0].insert(a[2][0].begin(), a[1][0][0]);
        a[2][0].insert(a[2][0].begin(), a[0][0][0]);
        return a[2][0];
    }
    if (j == m) {
        a[0][2].pop_back(), a[0][2].pop_back();
        a[0][2].insert(a[0][2].begin(), a[0][1][0]);
        a[0][2].insert(a[0][2].begin(), a[0][0][0]);
        return a[0][2];
    }
    return a[0][0];
}

Compilation message

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:59:10: warning: variable 'place' set but not used [-Wunused-but-set-variable]
   59 |     auto place = [&](int p, int q, int tm) {
      |          ^~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 2260 KB Output is correct
2 Correct 8 ms 2244 KB Output is correct
3 Correct 8 ms 2228 KB Output is correct
4 Correct 8 ms 2300 KB Output is correct
5 Correct 8 ms 2072 KB Output is correct
6 Correct 8 ms 2392 KB Output is correct
7 Correct 10 ms 2316 KB Output is correct
8 Correct 16 ms 2600 KB Output is correct
9 Correct 16 ms 2612 KB Output is correct
10 Correct 16 ms 2584 KB Output is correct
11 Correct 16 ms 2640 KB Output is correct
12 Correct 16 ms 2632 KB Output is correct
13 Correct 16 ms 2668 KB Output is correct
14 Correct 27 ms 2684 KB Output is correct
15 Correct 39 ms 2676 KB Output is correct
16 Correct 41 ms 2644 KB Output is correct
17 Correct 40 ms 2800 KB Output is correct
18 Correct 43 ms 2704 KB Output is correct
19 Correct 41 ms 2612 KB Output is correct
20 Correct 39 ms 2924 KB Output is correct
21 Incorrect 8 ms 348 KB Incorrect
22 Halted 0 ms 0 KB -