oj.uz

Submission #572816

# Submission time Handle Problem Language Result Execution time Memory
572816 2022-06-05T10:32:40 Z baluteshih Mars (APIO22_mars) C++17
21 / 100
 51 ms 2784 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) + 1;
    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 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2044 KB Output is correct
2 Correct 7 ms 1964 KB Output is correct
3 Correct 8 ms 2268 KB Output is correct
4 Correct 8 ms 2464 KB Output is correct
5 Correct 8 ms 2512 KB Output is correct
6 Correct 8 ms 2472 KB Output is correct
7 Correct 11 ms 2604 KB Output is correct
8 Correct 16 ms 2756 KB Output is correct
9 Correct 16 ms 2560 KB Output is correct
10 Correct 17 ms 2592 KB Output is correct
11 Correct 16 ms 2508 KB Output is correct
12 Correct 16 ms 2568 KB Output is correct
13 Correct 16 ms 2596 KB Output is correct
14 Correct 27 ms 2692 KB Output is correct
15 Correct 40 ms 2692 KB Output is correct
16 Correct 41 ms 2784 KB Output is correct
17 Correct 41 ms 2660 KB Output is correct
18 Correct 39 ms 2720 KB Output is correct
19 Correct 40 ms 2692 KB Output is correct
20 Correct 51 ms 2688 KB Output is correct
21 Incorrect 7 ms 344 KB Incorrect
22 Halted 0 ms 0 KB -