Submission #835529

#	Time	Username	Problem	Language	Result	Execution time	Memory
835529		HappyPacMan	Garden (JOI23_garden)	C++14	100 / 100	1700 ms	178180 KiB

garden

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
const int MAXD = 5e3;
bool checked[MAXD][MAXD];

int minimum_cells(int N, int M, int D, vector<int> P, vector<int> Q, vector<int> R, vector<int> S) {
    short cnt[D],must[D];
    vector<short> base[D];
    vector<pair<short,short> > added[D];
    memset(cnt,0,sizeof(cnt));
    memset(must,0,sizeof(must));
    short nxt[2*D],rev[2*D];
    for(int i=0;i<M;i++){
        checked[S[i]][R[i]] = true;
    }
	for(int i=0;i<D;i++){
        for(int j=0;j<D;j++){
            if(checked[i][j]){
                base[i].push_back(j);
            }
        }
		if(base[i].size()){
			for(int j=0,k=0;j<D;j++){
				added[j].emplace_back(i,base[i][(k-1+base[i].size())%base[i].size()]);
				if(j == base[i][k]){
					k++;
				}
			}
		}
	}
    for(int i=0;i<N;i++){
        must[P[i]] = true;
        cnt[Q[i]] = true;
    }
    short aaa = 0;
    for(short i=0;i<D;i++){
        aaa += must[i];
    }
    int ans = INF;
    for(short i=0;i<D;i++){
        memset(nxt,-1,sizeof(nxt));
        memset(rev,-1,sizeof(rev));
		vector<short> calc[D];
		for(auto [x,y] : added[i]){
			calc[y].push_back(x);
		}
        for(short j=0;j<D;j++){
            for(short it : calc[j]){
                cnt[it]++;
            }
        }
        vector<short> st;
        for(short j=0;j<D;j++){
            if(cnt[j]){
                st.push_back(j);
            }
        }
        for(short j=0;j<D;j++){
            if(cnt[j]){
                st.push_back(j+D);
            }
        }
        short last = -1, dist = 0;
        for(short it : st){
            if(last != -1){
                nxt[last] = it;
                rev[it] = last;
                dist = max(dist,(short)(it-last));
            }
            last = it;
        }
        short sum = 0;
        for(short j=0;j<D;j++){
            short k = i+j;
            if(k >= D){
                k -= D;
            }
            for(short it : calc[k]){
                cnt[it]--;
                if(cnt[it] == 0){
                    if(rev[it] != -1){
                        nxt[rev[it]] = nxt[it];
                    }
                    if(nxt[it] != -1){
                        rev[nxt[it]] = rev[it];
                    }
                    if(rev[it] != -1 && nxt[it] != -1){
                        dist = max(dist,(short)(nxt[it]-rev[it]));
                    }
                    if(rev[it+D] != -1){
                        nxt[rev[it+D]] = nxt[it+D];
                    }
                    if(nxt[it] != -1){
                        rev[nxt[it+D]] = rev[it+D];
                    }
                    if(rev[it+D] != -1 && nxt[it+D] != -1){
                        dist = max(dist,(short)(nxt[it+D]-rev[it+D]));
                    }
                }
            }
            sum += must[k];
            if(sum == aaa){
                ans = min(ans,(j+1)*(D-dist+1));
            }
        }
    }
    return ans;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N,M,D;
    cin >> N >> M >> D;
    vector<int> P(N),Q(N),R(M),S(M);
    for(int i=0;i<N;i++){
        cin >> P[i] >> Q[i];
    }
    for(int i=0;i<M;i++){
        cin >> R[i] >> S[i];
    }
    cout << minimum_cells(N,M,D,P,Q,R,S) << "\n";
}

Compilation message (stderr)

garden.cpp: In function 'int minimum_cells(int, int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
garden.cpp:45:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   45 |   for(auto [x,y] : added[i]){
      |            ^

• Subtask 1: 15 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 30 / 30
• Subtask 6: 25 / 25