oj.uz

Submission #572818

# Submission time Handle Problem Language Result Execution time Memory
572818 2022-06-05T10:33:45 Z baluteshih Mars (APIO22_mars) C++17
14 / 100
 16 ms 2684 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 = 5; 

    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 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct

Subtask #3
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #4
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #7
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #8
0.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #9
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -

Subtask #10
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 1808 KB Output is correct
2 Correct 8 ms 2180 KB Output is correct
3 Correct 8 ms 2272 KB Output is correct
4 Correct 8 ms 2444 KB Output is correct
5 Correct 8 ms 2288 KB Output is correct
6 Correct 7 ms 2300 KB Output is correct
7 Correct 9 ms 2520 KB Output is correct
8 Correct 16 ms 2536 KB Output is correct
9 Correct 16 ms 2684 KB Output is correct
10 Correct 16 ms 2516 KB Output is correct
11 Correct 16 ms 2564 KB Output is correct
12 Correct 16 ms 2588 KB Output is correct
13 Correct 16 ms 2632 KB Output is correct
14 Incorrect 3 ms 336 KB Incorrect
15 Halted 0 ms 0 KB -