Submission #668730

#	Time	Username	Problem	Language	Result	Execution time	Memory
668730		kenken714	Mars (APIO22_mars)	C++17	54 / 100	2155 ms	3632 KiB

mars

#include <bits/stdc++.h>

using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) { }
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

string solve1(string s, int n){//n ! 2n * 1
    UnionFind uni(5000);
    vector<bool> used(5000);
    ll ans = 0, ecnt = 0;
    REP(i, n * n){
        if(s[i] == '0')ecnt++;
    }
    REP(i, n){
        REP(j, n){
            if(s[i * n + j] != '1')continue;
            if(i != n - 1 and s[(i + 1) * n + j] == '1')uni.unionSet(i * n + j, (i + 1) * n + j);
            if(j != n - 1 and s[i * n + j + 1] == '1')uni.unionSet(i * n + j, i * n + j + 1);
        }
    }
    REP(i, n * n){
        if(!used[uni.root(i)]){
            used[uni.root(i)] = true;
            ans++;
        }
    }
    ans -= ecnt;
    string res;
    while(ans > 0){
        if(ans % 2 == 1)res.push_back('1');
        else res.push_back('0');
        ans /= 2;
    }
    while(res.size() < 100) res.push_back('0');
    return res;
}


P locate(ll x, ll y, ll n){
    ll m = 2 * n + 1, fi = (m + 2)/ 3, se = m - fi * 2, I, J, X, Y;
    if(x < fi) {
        I = 0;
        X = 0;
    }
    else if(x >= fi and x < fi * 2){
        I = 1;
        X = fi;
    }
    else {
        I = 2;
        X = fi * 2;
    }
    if(y < fi) {
        J = 0;
        Y = 0;
    }
    else if(y >= fi and y < fi * 2){
        J = 1;
        Y = fi;
    }
    else {
        J = 2;
        Y = fi * 2;
    }
    if(y < fi * 2){
        return P(I * 3 + J, fi * (x - X) + (y - Y));
    }
    else{
        return P(I * 3 + J, se * (x - X) + (y - Y));
    }
}

string process(vector<vector<string>> a, int gi, int gj, int gk, int n){
    ll m = 2 * n + 1, fi = (m + 2)/ 3, se = m - fi * 2;
    if(gk < n - 1){//kousin

        vector<vector<ll>> s(m, vector<ll>(m));//sim
        REP(i, m){
            ll I;
            if(i < fi) I = 0;
            else if(i >= fi and i < fi * 2)I = 1;
            else I = 2;
            REP(j, m){
                ll J;
                if(j < fi) J = 0;
                else if(j >= fi and j < fi * 2)J = 1;
                else J = 2;
                s[i][j] = I * 3 + J + 1;
            }
        }
		bool rok = false;
        REP(kkk, n){
            REP(i, m - 2 * (kkk + 1)){
                REP(j, m - 2 * (kkk + 1)){
                    if(i == gi and j == gj and kkk == gk){
						rok = true;
						break;
					}
                    ll nmin = 10;
                    REP(x, 3){
                        REP(y, 3){
                            if(s[i + x][j + y] > 0 and nmin > s[i + x][j + y]){
                                nmin = s[i + x][j + y];
                            }
                        }
                    }
                    if(nmin == 10)continue;
                    if(s[i][j] != 0)nmin = s[i][j];
                    REP(x, 3){
                        REP(y, 3){
                            if(x == 0 and y == 0)continue;
                            if(s[i + x][j + y] == nmin){
                                s[i + x][j + y] = 0;
                            }
                        }
                    }
                    s[i][j] = nmin;
                }
				if(rok)break;
            }
			if(rok)break;
        }
			//cout << gi << " " << gj << " " << gk << " !!!"<<endl;
        //kousin
        ll nmin = 10;
        REP(x, 3){
            REP(y, 3){
                if(s[gi + x][gj + y] > 0 and nmin > s[gi + x][gj + y]){
                    nmin = s[gi + x][gj + y];
                }
            }
        }
        if(nmin == 10){//'0'
            string res(100, '0');
            return res;
        }
        if(s[gi][gj] != 0){
            nmin = s[gi][gj];
            if(gk == 0) swap(a[0][0][locate(gi, gj, n).second], a[0][0][0]);
        }
		else{
			 REP(d, 100) a[0][0][d] = '0';
		}
        REP(x, 3){
            REP(y, 3){
                if(x == 0 and y == 0)continue;
                if(s[gi + x][gj + y] == nmin){
                    if(gk == 0) swap(a[x][y][locate(gi + x, gj + y, n).second], a[x][y][0]);
                    REP(d, 100) if(a[x][y][d] == '1')a[0][0][d] = '1';
                }
            }
        }
		//cout << a[0][0] <<endl;
        return a[0][0];
    }
    else {//last
        string mp;
        REP(i, m){//init
            REP(j, m){
                P pos = locate(i, j, n);
                mp.push_back(a[pos.first / 3][pos.first % 3][pos.second]);
				//cout << i <<" " << j << "  ! " << pos.first / 3 << " " << pos.first % 3 << " " << pos.second <<" " << a[pos.first / 3][pos.first % 3][pos.second]<<endl;
            }
        }
        string res = solve1(mp, m);
        return res;
    }
}


 

Compilation message (stderr)

mars.cpp: In function 'std::string process(std::vector<std::vector<std::__cxx11::basic_string<char> > >, int, int, int, int)':
mars.cpp:106:40: warning: unused variable 'se' [-Wunused-variable]
  106 |     ll m = 2 * n + 1, fi = (m + 2)/ 3, se = m - fi * 2;
      |                                        ^~

• 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: 0 / 24
• Subtask 9: 0 / 11
• Subtask 10: 0 / 11