/ SeriousOJ /

Record Detail

Memory Exceeded


  
# Status Time Cost Memory Cost
#1 Accepted 1ms 540.0 KiB
#2 Accepted 35ms 576.0 KiB
#3 Accepted 34ms 556.0 KiB
#4 Accepted 43ms 804.0 KiB
#5 Accepted 56ms 796.0 KiB
#6 Accepted 201ms 2.094 MiB
#7 Time Exceeded ≥1107ms ≥147.465 MiB
#8 Memory Exceeded ≥194ms ≥256.016 MiB

Code

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

typedef long long ll;
#define bug(x) cout<<#x<<" : "<<x<<endl;
#define bug2(a,b) cout<<#a<<" : "<<a<<"\t"<<#b<<" : "<<b<<endl;

int n;
string a,b;
map<string,int>mp;

int f(int i,char last){
	if(i==n){
		return 1;
	}
	string cur=string(i,1)+":"+string(last,1);
	if(mp.find(cur)!=mp.end())return mp[cur];
	int ans=0;
	if(last<=b[i])ans=max(ans,f(i+1,b[i]));
	if(last<=a[i])ans=max(ans,f(i+1,a[i]));
	string cur1=string(i,1)+":"+string(last,1);
	return mp[cur1]=ans;
	return ans;
}
signed main(){
	
	ll t=1;cin>>t;
	while(t--){
		cin>>n;
		cin>>a>>b;
		string tmpa="",tmpb="";
		char last='#';
		mp.clear();
		// for(int i=0;i<n;i++){
		// 	if(a[i]<=b[i] and last<=a[i]){
		// 		last=a[i];
		// 		tmpa+=a[i];
		// 	}
		// 	else if(a[i]>=b[i] and last<=b[i]){
		// 		last=b[i];
		// 		tmpa+=b[i];
		// 	}
		// 	bug(last)
		// }
		// for(int i=0;i<n;i++){
		// 	if(a[i]<b[i])tmpb+=a[i];
		// 	else tmpb+=b[i];
		// }

		// bug(tmpa)
		// bug(tmpb)
		// if(is_sorted(tmpa.begin(),tmpa.end()))ok=1;
		int ok=f(0,'#');
		// if(is_sorted(tmpb.begin(),tmpb.end()))ok=1;
		if(ok)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}

Information

Submit By
Type
Submission
Problem
P1117 String Sorted
Contest
LU IUJPC : Sylhet Division 2024, Mock Round
Language
C++17 (G++ 13.2.0)
Submit At
2024-12-07 10:26:50
Judged At
2024-12-07 10:26:50
Judged By
Score
40
Total Time
≥1107ms
Peak Memory
≥256.016 MiB