Submission #1209611

#	Time	Username	Problem	Language	Result	Execution time	Memory
1209611		garam1732	여왕벌 (KOI15_queen)	C++20	0 / 100	234 ms	589824 KiB

Main

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define bl ' '
#define endl '\n'
#define all(v) (v).begin(), (v).end()
#define comp(v) (v).erase(unique(all(v)), (v).end())
#define lbd(v,x) lower_bound(all(v), (x))-(v).begin()
#define ubd(v,x) upper_bound(all(v), (x))-(v).begin()

typedef long long ll;
typedef pair<int, int> pi;
typedef pair<pi, int> pii;
typedef pair<int, pi> ipi;
typedef pair<pi, pi> pipi;
typedef pair<ll, ll> pll;

const int MAXN = 100100*10;
const ll MOD = 998244353;
const ll INF = 1e16;

const int MAXM = 770;
string info[MAXM][MAXM];

typedef array<int,3> Bee;

const int MAXSZ = MAXM*MAXM*10;
map<int, int> mp[MAXSZ];
map<int, int> dp[MAXSZ];
map<int, int> w[MAXSZ][4];
int sz=0;

map<Bee, int> bee;
vector<Bee> arr;
int num;

int res[MAXM][MAXM];
int nn;

void dnc(int sx, int ex, int sy, int ey, int t) {
    // cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" mp : "<<endl;
    // for(auto [x,cnt] : mp[t]) {            
    //         cout<<x[0]<<bl<<x[1]<<bl<<x[2]<<bl<<cnt<<endl;
    //     } 
    if(sx==ex || sy==ey) {
        for(auto [x,cnt] : mp[t]) {
            dp[t][x] = x;
        } return;
    }
    if(sx+1==ex && sy+1==ey) {
        for(auto [x,cnt] : mp[t]) {
            int idx;
            if(arr[x][0]==3) idx=0;
            else if(arr[x][0]==2 && arr[x][1]==1) idx=1;
            else if(arr[x][0]==2) idx=2;
            else if(arr[x][0]==1 && arr[x][1]==2) idx=4;
            else if(arr[x][0]==1 && arr[x][2]==2) idx=8;
            else if(arr[x][0]==1) idx=5;
            else if(arr[x][1]==3) idx=13;
            else if(arr[x][1]==2) idx=14;
            else if(arr[x][1]==1) idx=17;
            else idx=26;

            int col;
            if(info[ex][ey][idx] == 'L') col=idx/9;
            else if(info[ex][ey][idx] == 'D') col=idx/3%3;
            else col=idx%3;

            res[ex][ey] += col*cnt;

            Bee y = {0,0,0};
            y[col]++; y[idx/9]++; y[idx%3]++;

            if(bee.find(y)==bee.end()) {
                arr.push_back(y);
                bee[y]=num++;
            } dp[t][x] = bee[y];
        } 

    //     cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" dp : "<<endl;
    // for(auto [x,y] : dp[sz]) {            
    //         cout<<x.a<<bl<<x.b<<bl<<x.c<<bl<<y.a<<bl<<y.b<<bl<<y.c<<endl;
    //     } 

        return;
    }

    int mx=sx+ex>>1, my=sy+ey>>1;
    for(auto [x, cnt] : mp[t]) {
        Bee y = {0,0,0};
        int tot = mx-sx+my-sy+1;
        y[0] = min(tot, max(0, arr[x][0]-(ex-mx)));
        y[2] = min(tot, max(0, arr[x][2]-(ey-my)));
        y[1] = tot-y[0]-y[2];

        if(bee.find(y)==bee.end()) {
            arr.push_back(y);
            bee[y]=num++;
        } mp[sz][bee[y]] += cnt;
        w[t][0][x] = bee[y];
    } int mx1 = sz++;
    dnc(sx, mx, sy, my, mx1);

    for(auto [x, cnt] : mp[t]) {//if(sx==0&&mx==0&&my==2&&ey==3)cout<<"YEE"<<endl;
        Bee y = {0,0,0};
        int tot1 = mx-sx+1, tot2 = ey-my;
        y[0] = min(tot1, max(0, arr[dp[mx1][w[t][0][x]]][0]-(my-sy))) + min(tot2, max(0, arr[x][0]-(ex-sx+my-sy+1)));
        y[2] = min(tot1, arr[dp[mx1][w[t][0][x]]][2]) + min(tot2, arr[x][2]);
        y[1] = tot1+tot2-y[0]-y[2];
    
        if(bee.find(y)==bee.end()) {
            arr.push_back(y);
            bee[y]=num++;
        } mp[sz][bee[y]] += cnt;
        w[t][1][x] = bee[y];
    } int mx2 = sz++;
    dnc(sx, mx, my, ey, mx2);

    for(auto [x, cnt] : mp[t]) {//if(mx+1==2&&ex==2&&sy==3&&my==3)cout<<"Yee"<<dp[mx1][w[t][0][x]].c<<endl;
        Bee y = {0,0,0};
        int tot1 = ex-mx, tot2 = my-sy+1;
        y[0] = min(tot1, arr[x][0]) + min(tot2, arr[dp[mx1][w[t][0][x]]][0]);
        y[2] = min(tot1, max(0, arr[x][2]-(ey-sy+mx-sx+1))) + min(tot2, max(0, arr[dp[mx1][w[t][0][x]]][2]-(mx-sx)));
        y[1] = tot1+tot2-y[0]-y[2];
        
        if(bee.find(y)==bee.end()) {
            arr.push_back(y);
            bee[y]=num++;
        } mp[sz][bee[y]] += cnt;
        w[t][2][x] = bee[y];
    } int mx3 = sz++;
    dnc(mx, ex, sy, my, mx3);

    for(auto [x, cnt] : mp[t]) {
        Bee y = {0,0,0};
        int tot1 = ex-mx+1, tot2 = ey-my;
        y[0] = min(tot1, max(0, arr[dp[mx3][w[t][2][x]]][0]-(my-sy))) + min(tot2, max(0, arr[dp[mx2][w[t][1][x]]][0]-1));
        y[2] = min(tot1, arr[dp[mx3][w[t][2][x]]][2]) + min(tot2, max(0, arr[dp[mx2][w[t][1][x]]][2]-(mx-sx)));
        y[1] = tot1+tot2-y[0]-y[2];
        
        if(bee.find(y)==bee.end()) {
            arr.push_back(y);
            bee[y]=num++;
        } mp[sz][bee[y]] += cnt;
        w[t][3][x] = bee[y];
    } int mx4 = sz++;
    dnc(mx, ex, my, ey, mx4);

    for(auto [x, cnt] : mp[t]) {//if(sx==1&&ex==2&&sy==3&&ey==3) cout<<"YEE"<<dp[mx2][w[t][1][x]].a-(ey-my-1)<<endl;
        Bee y = {0,0,0};
        int tot1 = my-sy, tot2 = mx-sx, tot3 = ex-mx+ey-my+1;
        y[0] = min(tot1, arr[dp[mx3][w[t][2][x]]][0]) + min(tot2, max(0, arr[dp[mx2][w[t][1][x]]][0]-(ey-my+1))) + arr[dp[mx4][w[t][3][x]]][0];
        y[2] = min(tot1, max(0, arr[dp[mx3][w[t][2][x]]][2]-(ex-mx+1))) + min(tot2, arr[dp[mx2][w[t][1][x]]][2]) + arr[dp[mx4][w[t][3][x]]][2];
        y[1] = tot1+tot2+tot3-y[0]-y[2];
        
        if(bee.find(y)==bee.end()) {
            arr.push_back(y);
            bee[y]=num++;
        } dp[t][x] = bee[y];
    }

    // cout<<sx<<bl<<ex<<bl<<sy<<bl<<ey<<" dp : "<<endl;
    // for(auto [x,y] : dp[sz-1]) {            
    //         cout<<x.a<<bl<<x.b<<bl<<x.c<<bl<<y.a<<bl<<y.b<<bl<<y.c<<endl;
    //     } 
    return;
}

vector<pi> v;
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);

    int m, n; cin>>m>>n;
    for(int i=1; i<m; i++) {
        for(int j=1; j<m; j++) {
            cin >> info[i][j];
        }
    }

    for(int i=m-1; i; i--) v.push_back(pi(i, 0));
    for(int j=0; j<m; j++) v.push_back(pi(0, j));
    assert(v.size() == 2*m-1);

    for(int i=0; i<n; i++) {
        int a,b,c; cin>>a>>b>>c;

        if(bee.find({a,b,c})==bee.end()) {
            arr.push_back({a,b,c});
            bee[{a,b,c}] = num++;
        } mp[sz][bee[{a,b,c}]]++;

        int x=0;
        while(a--) {
            pi t=v[x++]; res[t.ff][t.ss] += 0;
        } while(b--) {
            pi t=v[x++]; res[t.ff][t.ss] += 1;
        } while(c--) {
            pi t=v[x++]; res[t.ff][t.ss] += 2;
        }
    } sz++;

    //dnc(0, m-1, 0, m-1, 0);

    for(int i=0; i<m; i++) {
        for(int j=0; j<m; j++) cout<<res[i][j]+1<<bl;
        cout<<endl;
    }
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 24
• Subtask 3: 0 / 34
• Subtask 4: 0 / 32