Submission #1263863

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263863		Zbyszek99	화성 (APIO22_mars)	C++20	100 / 100	636 ms	6264 KiB

mars

#include "mars.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int rep_[100000];
int min_row[100000];
int min_col[100001];


int fint(int v)
{
    if(rep_[v] == v) return v;
    rep_[v] = fint(rep_[v]);
    return rep_[v];
}

void onion(int a, int b)
{
    a = fint(a);
    b = fint(b);
    min_row[a] = min(min_row[a],min_row[b]);
    min_col[a] = min(min_col[a],min_col[b]);
    rep_[b] = a;
}

void upd(int** grid, int n, vi comps, int& ans, vi& ans_segs, int& zost)
{
    rep(i,n)
    {
        rep(j,n)
        {
            int v = i*n+j;
            min_col[v] = j;
            min_row[v] = i;
            rep_[v] = v;
        }
    }
    vector<pii> segs;
    pii prev = {n-1,2};
    for(int i = n-1; i >= 3; i--)
    {
        if(grid[i][2] == 0)
        {
            if(!(prev.ff == i && prev.ss == 2))
            {
                rep2(k,prev.ff+1,i-1)
                {
                    onion(k*n+2,(k+1)*n+2);
                }
                segs.pb(prev);
            }
            prev = {i-1,2};
        }
    }
    for(int j = 2; j < n; j++)
    {
        if(grid[2][j] == 0)
        {
            if(!(prev.ff == 2 && prev.ss == j))
            {
                if(prev.ff == 2)
                {
                    rep2(k,prev.ss+1,j-1)
                    {
                        onion(2*n+k,2*n+k-1);
                    }
                }
                else
                {
                    rep2(k,prev.ff+1,2)
                    {
                        onion(k*n+2,(k+1)*n+2);
                    }
                    rep2(k,prev.ss+1,j-1)
                    {
                        onion(2*n+k,2*n+k-1);
                    }
                }
                segs.pb(prev);
            }
            prev = {2,j+1};
        }
    }
    if(!(prev.ff== 2 && prev.ss == n))
    {
        rep2(k,prev.ss+1,n-1)
        {
            onion(2*n+k,2*n+k-1);
        }
        segs.pb(prev);
    }
    map<int,int> prev_same;
    rep(j,n+3) prev_same[j] = -1;
    int cur_sum = 0;
    rep(i,siz(segs))
    {
        int com = comps[i];
        if(com == 3)
        {
            continue;
        }
        if(com == 0)
        {
            if(prev_same[cur_sum] != -1) onion(segs[i].ff*n+segs[i].ss,prev_same[cur_sum]);
        }
        if(com == 1)
        {
            cur_sum++;
            prev_same[cur_sum] = segs[i].ff*n+segs[i].ss;
        }
        if(com == 2)
        {
            onion(segs[i].ff*n+segs[i].ss,prev_same[cur_sum]);
            prev_same[cur_sum] = -1;
            cur_sum--;
        }
    }
    vector<pii> dirs = {{0,1},{0,-1},{1,0},{-1,0}};
    rep(i,n)
    {
        rep(j,n)
        {
            forall(it,dirs)
            {
                int i2 = i+it.ff;
                int j2 = j+it.ss;
                if(i2 >= 0 && i2 <= n-1 && j2 >= 0 && j2 < n && grid[i][j] == 1 && grid[i2][j2] == 1)
                {
                    onion(i*n+j,i2*n+j2);
                }
            }
        }
    }
    set<int> rest;
    rep(i,n)
    {
        rep(j,n)
        {
            if(fint(i*n+j) == i*n+j && grid[i][j] == 1)
            {
                int v = i*n+j;
                if(min_col[v] != 0 && min_row[v] != 0) ans++;
                else rest.insert(v);
            }
        }
    }
    zost = siz(rest);
    segs = {};
    prev = {n-1,0};
    for(int i = n-1; i >= 1; i--)
    {
        if(grid[i][0] == 0)
        {
            if(!(prev.ff == i && prev.ss == 0))
            {
                segs.pb(prev);
            }
            prev = {i-1,0};
        }
    }
    for(int j = 0; j < n; j++)
    {
        if(grid[0][j] == 0)
        {
            if(!(prev.ff == 0 && prev.ss == j))
            {
                segs.pb(prev);
            }
            prev = {0,j+1};
        }
    }
    if(!(prev.ff == 0 && prev.ss == n))
    {
        segs.pb(prev);
    }
    set<int> was;
    map<int,int> cnt;
    map<int,int> cnt2;
    forall(it,segs) 
    {
        cnt[fint(it.ff*n+it.ss)]++;
        cnt2[fint(it.ff*n+it.ss)]++;
    }
    stack<int> pop;
    pop.push(-1);
    forall(it,segs)
    {
        int v = fint(it.ff*n+it.ss);
        cnt2[v]--;
        if(cnt[v] == 1)
        {
            ans_segs.pb(3);
            continue;
        }
        if(was.find(v) == was.end())
        {
            ans_segs.pb(1);
            pop.push(v);
            was.insert(v);
            continue;
        }
        if(pop.top() == v && cnt2[v] != 0)
        {
            ans_segs.pb(0);
            continue;
        }
        ans_segs.pb(2);
        pop.pop();
    }    
}

string process(vector<vector<string>> a, int i, int j, int k, int n)
{
    if(!(i == 2*(n-k-1) || j == 2*(n-k-1))) 
    {
        string s;
        rep(i,100) s += '0';
        s[0] = a[0][0][0];
        return s;
    }
	if(i == j)
    {
        string my_ans;
        rep(i,100) my_ans += "0";
        int prev_ans = 0;
        rep2(i,90,99)
        {
            if(a[2][2][i] == '1') prev_ans += (1 << (i-90));
        }
        int** grid;
        int d = k*2+3;
        grid = new int*[d];
        rep(i,d) grid[i] = new int[d];
        rep(i,d) rep(j,d) grid[i][j] = 0;
        grid[0][0] = (a[0][0][0] == '1' ? 1 : 0);
        grid[1][0] = (a[1][0][0] == '1' ? 1 : 0);
        grid[0][1] = (a[0][1][0] == '1' ? 1 : 0);
        grid[1][1] = (a[1][1][0] == '1' ? 1 : 0);
        vi coms;
        rep3(i,0,88,2)
        {
            int v1 = (a[2][2][i] == '1' ? 1 : 0);
            int v2 = (a[2][2][i+1] == '1' ? 1 : 0);
            coms.pb(v1+v2*2);
        }
        if(k != 0)
        {
            int s = d;
            rep2(i,2,d-1)
            {
                grid[i][0] = (a[2][0][i-2] == '1' ? 1 : 0);
            }
            rep2(i,2,d-1)
            {
                grid[i][1] = (a[2][1][i-2] == '1' ? 1 : 0);
            }
            rep2(i,2,d-1)
            {
                grid[i][2] = (a[2][1][i-2+s-2] == '1' ? 1 : 0);
            }
            rep2(i,2,d-1)
            {
                grid[0][i] = (a[0][2][i-2] == '1' ? 1 : 0);
            }
            rep2(i,2,d-1)
            {
                grid[1][i] = (a[1][2][i-2] == '1' ? 1 : 0);
            }
            rep2(i,2,d-1)
            {
                grid[2][i] = (a[1][2][i-2+s-2] == '1' ? 1 : 0);
            }
        }
        else
        {
            rep(i,3)
            {
                rep(j,3)
                {
                    grid[i][j] = (a[i][j][0] == '1' ? 1 : 0);
                }
            }
        }
        vi new_coms;
        int zost;
        upd(grid,d,coms,prev_ans,new_coms,zost);
        if(k == n-1)
        {
            prev_ans += zost;
            rep(bit,10)
            {
                if(prev_ans & (1 << bit))
                {
                    my_ans[bit] = '1';
                }
            }
            return my_ans;
        }
        rep(i,siz(new_coms))
        {
            int v1 = new_coms[i]%2;
            int v2 = new_coms[i]/2;
            if(v1 == 1) my_ans[i*2] = '1';
            if(v2 == 1) my_ans[i*2+1] = '1';
        }
        rep2(bit,90,99)
        {
            if(prev_ans & (1 << (bit-90))) my_ans[bit] = '1';
        }
        return my_ans;
    }
    else if(i > j)
    {
        string a2;
        int s = k*2+1;
        a2 = a[0][0][0];
        a2 += a[1][0][0];
        rep(i,s) a2 += a[2][0][i];
        a2 += a[0][1][0];
        a2 += a[1][1][0];
        rep(i,s)
        {
            a2 += a[2][1][i];
        }
        int d = 100-siz(a2);
        rep(i,d) a2 += "0";
        return a2;
    }
    else
    {
        string a2;
        int s = k*2+1;
        a2 = a[0][0][0];
        a2 += a[0][1][0];
        rep(i,s) a2 += a[0][2][i];
        a2 += a[1][0][0];
        a2 += a[1][1][0];
        rep(i,s)
        {
            a2 += a[1][2][i];
        }
        int d = 100-siz(a2);
        rep(i,d) a2 += "0";
        return a2;
    }
}

• 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