Submission #573878

#	Time	Username	Problem	Language	Result	Execution time	Memory
573878		somethingnew	Mars (APIO22_mars)	C++17	100 / 100	1275 ms	4784 KiB

mars

#include "mars.h"
#include <iostream>
#include "vector"
#include "algorithm"
#include "numeric"
#include "climits"
#include "iomanip"
#include "bitset"
#include "cmath"
#include "map"
#include "deque"
#include "array"
#include "set"
#define all(x) x.begin(), x.end()
using namespace std;
pair<string, string> topairstr(vector<int> nums, string line) {
    string opn(line.size(), '0'), cls(line.size(), '0');
    int ind = 0;
    map<int, int> lstps;
    for (int i = 0; i < nums.size(); ++i) {
        //cout << nums[i] << ' ';
        if (line[i] == '1' and (i == 0 or line[i-1] != '1')) {
            if (lstps.find(nums[i]) != lstps.end()) {
                cls[ind] = '1';
                opn[lstps[nums[i]]] = '1';
            }
            lstps[nums[i]] = ind;
            ind++;
        }
    }
    //cout << endl;
    //cout << opn << endl << cls << endl << line << ' ' << "AMOG" << endl;
    return {opn, cls};
}
vector<int> tovec(pair<string, string> ss, string line) {
    auto [opn, cls] = ss;
    vector<int> a(line.size());
    vector<int> stk;
    int nm = 0;
    int ind = 0;
    for (int i = 0; i < line.size(); ++i) {
        if (line[i] == '1' and (i == 0 or line[i-1] != '1')) {
            int thisnum;
            if (cls[ind] == '1') {
                thisnum = stk.back();
                stk.pop_back();
            } else {
                thisnum = nm++;
            }
            a[i] = thisnum;
            if (opn[ind] == '1')
                stk.push_back(thisnum);
            ind++;
        } else if (line[i] == '1') {
            a[i] = a[i - 1];
        }
    }
    return a;
}
int getnuminstr(string a) {
    int res = 0;
    for (int i = 90; i < 100; ++i) {
        res += (a[i] == '1') << (i - 90);
    }
    return res;
}
void chnuminstr(string &a, int res) {
    for (int i = 90; i < 100; ++i) {
        if (res & (1 << (i - 90)))
            a[i] = '1';
        else
            a[i] = '0';
    }
}
string get1str(string a) {
    string b;
    for (int i = 1; i < 45; ++i) {
        b += a[i];
    }
    return b;
}
string get2str(string a) {
    string b;
    for (int i = 45; i < 90; ++i) {
        b += a[i];
    }
    return b;
}

void ch1str(string &a, string b) {
    for (int i = 1; i < 45; ++i) {
        if (b.size() <= i - 1)
            continue;
        a[i] = b[i-1];
    }
}
void ch2str(string &a, string b) {
    for (int i = 45; i < 90; ++i) {
        if (b.size() <= i - 45)
            continue;
        a[i] = b[i-45];
    }
}
struct snm{
    vector<int> p;
    int cnt;
    void init(int n) {
        cnt = n;
        p.assign(n, {});
        for (int i = 0; i < n; ++i) {
            p[i] = i;
        }
    }
    int getv(int v) {
        if (p[v] == v)
            return v;
        return p[v] = getv(p[v]);
    }
    void merge(int a, int b) {
        a = getv(a);b = getv(b);
        if (a != b) {
            cnt--;
            p[a] = b;
        }
    }
};
string resstring(string a) {
    string s(100, '0');
    for (int i = 90; i < 100; ++i) {
        s[i-90] = a[i];
    }
    return s;
}
string solvepole(int n, vector<vector<string>> a, int iszero) {
    vector<vector<int>> pole(n, vector<int>(n)), pole2(n, vector<int>(n, -1));
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 3; ++j) {
            pole[i][j] = a[i][j][0] - '0';
        }
    }
    string si0 = get1str(a[2][0]);
    string si1 = get1str(a[2][1]);
    string si2 = get2str(a[2][1]);
    string s0j = get1str(a[0][2]);
    string s1j = get1str(a[1][2]);
    string s2j = get2str(a[1][2]);
    for (int i = 3; i < n; ++i) {
        int pstr = n - 1 - i;
        pole[i][0] = si0[pstr] - '0';
        pole[i][1] = si1[pstr] - '0';
        pole[i][2] = si2[pstr] - '0';
        pole[0][i] = s0j[pstr] - '0';
        pole[1][i] = s1j[pstr] - '0';
        pole[2][i] = s2j[pstr] - '0';
    }

    //cout << a[2][2] << endl;
    string opn = get1str(a[2][2]), cls = get2str(a[2][2]);
    string zeroone;
    for (int i = n - 1; i >= 2; --i) {
        zeroone.push_back(pole[i][2] + '0');
    }
    for (int j = 3; j < n; ++j) {
        zeroone.push_back(pole[2][j] + '0');
    }
    //cout << opn << endl;
    //cout << cls << endl;
    //cout << zeroone << endl;
    vector<int> nums = tovec({opn, cls}, zeroone);
    snm sm;
    int res = getnuminstr(a[2][2]);
    //cout << res << endl;
    int sled = 0;
    //cout << "NUMS ";
    //for (auto i : nums)
    //    cout << i << ' ';
    //cout << endl;
    for (int i = 0; i < zeroone.size(); ++i) {
        if (zeroone[i] == '1')
            sled = max(sled, nums[i] + 1);
    }
    reverse(all(nums));
    for (int i = n - 1; i >= 2; --i) {
        if (pole[i][2] == 1) {
            pole2[i][2] = nums.back();
        }
        nums.pop_back();
    }
    for (int j = 3; j < n; ++j) {
        if (pole[2][j] == 1) {
            pole2[2][j] = nums.back();
        }
        nums.pop_back();
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (pole[i][j] == 1) {
                if (pole2[i][j] == -1) {
                    pole2[i][j] = sled++;
                }
            }
        }
    }
    snm dsu;
    dsu.init(sled);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (pole[i][j] == 1) {
                if (i+1 != n and pole[i+1][j] == 1) {
                    dsu.merge(pole2[i][j], pole2[i+1][j]);
                }
                if (j+1 != n and pole[i][j+1] == 1) {
                    dsu.merge(pole2[i][j], pole2[i][j+1]);
                }
            }
        }
    }
    res += dsu.cnt;
    set<int> kr;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (pole[i][j]) {
                pole2[i][j] = dsu.getv(pole2[i][j]);
                if (i == 0 or j == 0)
                    kr.insert(pole2[i][j]);
            }
        }
    }
    if (!iszero)
        res -= kr.size();
    chnuminstr(a[0][0], res);
    zeroone.clear();
    nums.clear();
    for (int i = n - 1; i >= 0; --i) {
        zeroone.push_back(pole[i][0] + '0');
        nums.push_back(pole2[i][0]);
    }
    for (int j = 1; j < n; ++j) {
        zeroone.push_back(pole[0][j] + '0');
        nums.push_back(pole2[0][j]);
    }

    if (iszero)
        return resstring(a[0][0]);
    auto [opn2, cls2] = topairstr(nums, zeroone);
    ch1str(a[0][0], opn2);
    ch2str(a[0][0], cls2);
    return a[0][0];
}
string process(vector <vector<string>> a, int i, int j, int k, int n) {
    if (((n - k - 1) * 2 + 1 > i and (n - k - 2) * 2 + 1 < i) or ((n - k - 1) * 2 + 1 > j and (n - k - 2) * 2 + 1 < j)) {
        //cerr << i << ' ' << j << ' ' << k << endl;
        if (i == j) {
            string s = solvepole(2 * n + 1 - i, a, i == 0);
            return s;
        }
        if (i < j) {
            string s1 = get1str(a[0][2]);
            string s2 = get2str(a[0][2]);
            s1[2*(n-1)-j] = a[0][2][0];
            s1[2*(n-1)-j+1] = a[0][1][0];
            s2[2*(n-1)-j] = a[1][2][0];
            s2[2*(n-1)-j+1] = a[1][1][0];
            ch1str(a[0][0], s1);
            ch2str(a[0][0], s2);
        } else {
            string s1 = get1str(a[2][0]);
            string s2 = get2str(a[2][0]);
            s1[2*(n-1)-i] = a[2][0][0];
            s1[2*(n-1)-i+1] = a[1][0][0];
            s2[2*(n-1)-i] = a[2][1][0];
            s2[2*(n-1)-i+1] = a[1][1][0];
            ch1str(a[0][0], s1);
            ch2str(a[0][0], s2);
        }
        return a[0][0];
    } else {
        return a[0][0];
    }
}

Compilation message (stderr)

mars.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> > topairstr(std::vector<int>, std::string)':
mars.cpp:20:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < nums.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
mars.cpp: In function 'std::vector<int> tovec(std::pair<std::__cxx11::basic_string<char>, std::__cxx11::basic_string<char> >, std::string)':
mars.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < line.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~
mars.cpp: In function 'void ch1str(std::string&, std::string)':
mars.cpp:92:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   92 |         if (b.size() <= i - 1)
      |             ~~~~~~~~~^~~~~~~~
mars.cpp: In function 'void ch2str(std::string&, std::string)':
mars.cpp:99:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   99 |         if (b.size() <= i - 45)
      |             ~~~~~~~~~^~~~~~~~~
mars.cpp: In function 'std::string solvepole(int, std::vector<std::vector<std::__cxx11::basic_string<char> > >, int)':
mars.cpp:178:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  178 |     for (int i = 0; i < zeroone.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 7 / 7
• Subtask 4: 8 / 8
• Subtask 5: 7 / 7
• Subtask 6: 8 / 8
• Subtask 7: 10 / 10
• Subtask 8: 24 / 24
• Subtask 9: 11 / 11
• Subtask 10: 11 / 11