Submission #996574

#	Time	Username	Problem	Language	Result	Execution time	Memory
996574		MilosMilutinovic	Card Collection (JOI24_collection)	C++14	71 / 100	4069 ms	26968 KiB

Main

#include<bits/stdc++.h>
 
#define pb push_back
#define fi first
#define se second
#define mp make_pair
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
 
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
 
ll readint(){
	ll x=0,f=1; char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

int n,m;
int a[200005],b[200005],c[200005],d[200005];
bool dp[200005][10][10];
int mrg[15][15][2];

int main(){
	for(int t=0;t<2;t++){
		for(int p=0;p<15;p++){
			for(int q=0;q<15;q++){
				int ap=p/3,bp=p%3;
				int aq=q/3,bq=q%3;
				int a,b;
				if(t==0) a=min(ap,aq),b=min(bp,bq);
				if(t==1) a=max(ap,aq),b=max(bp,bq); 
				mrg[p][q][t]=a*3+b;
			}
		}
	}
	n=readint(); m=readint();
	for(int i=1;i<=n;i++) a[i]=readint(),b[i]=readint();
	for(int j=1;j<=m;j++){
		int x=readint(),y=readint();
		for(int i=1;i<=n;i++){
			c[i]=(a[i]<x?0:(a[i]==x?1:2));
			d[i]=(b[i]<y?0:(b[i]==y?1:2));
		}
		for(int i=1;i<=n;i++){
			for(int p=0;p<10;p++){
				for(int q=0;q<10;q++){
					dp[i][p][q]=false;
				}
			}
		}
		dp[1][c[1]*3+d[1]][9]=true;
		for(int i=2;i<=n;i++){
			int val=c[i]*3+d[i];
			for(int p=0;p<9;p++){
				for(int q=0;q<10;q++){
					if(!dp[i-1][p][q]) continue;
					vector<int> cards;
					if(q==9){
						dp[i][p][val]=true;
					}
					if(q==9){
						dp[i][mrg[p][val][0]][9]=true;
						dp[i][mrg[p][val][1]][9]=true;
					}	
					if(q!=9){
						dp[i][p][mrg[q][val][0]]=true;
						dp[i][p][mrg[q][val][1]]=true;
						dp[i][mrg[p][mrg[q][val][0]][0]][9]=true;
						dp[i][mrg[p][mrg[q][val][1]][0]][9]=true;
						dp[i][mrg[p][mrg[q][val][0]][1]][9]=true;
						dp[i][mrg[p][mrg[q][val][1]][1]][9]=true;
					}
				}
			}
		}
		if(dp[n][4][9]) printf("%d ",j);
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 38 / 38
• Subtask 3: 22 / 22
• Subtask 4: 0 / 29