제출 #1300494

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1300494		NotLinux	Devil's Share (RMI19_devil)	C++20	27 / 100	1596 ms	5124 KiB

devil

#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
int k,cnt[9];
pair<string,string> pai;
string str;
void dfs(int x){
	if(x == 0){
		string maxi;
		for(int i = 0;i+k-1<sz(str);i++){
			string cand = str.substr(i , i + k);
			if(maxi.empty() or maxi < cand)maxi = cand;
		}
		if(pai.first.empty() or pai.first > maxi){
			pai = {maxi , str};
		}
		return;
	}
	for(int i = 0;i<9;i++){
		if(cnt[i]){
			cnt[i]--;
			str += to_string(i+1);
			dfs(x-1);
			str.pop_back();
			cnt[i]++;
		}
	}
}
void solve(){
	pai = {"",""};
	str = "";
	cin >> k;
	int sum = 0;
	for(int i = 0;i<9;i++){
		cin >> cnt[i];
		sum += cnt[i];
	}
	
	if(k == 2){
		deque<int>arr(3*sum , -1);
		int sayac = 1 , maxi = -1;
		for(int i = 8;i>=0;i--){
			if(cnt[i]){
				maxi = i;
				if(cnt[maxi] == 1){
					// cerr << "flag0" << '\n';
					int scndmax = -1;
					for(int j = i-1;j>=0;j--)if(cnt[j]){
						scndmax = j;
						break;
					}
					for(int j = 0;j<scndmax;j++){
						while(cnt[j]--){
							if(arr[sayac] != -1)sayac += 2;
							arr[sayac] = j;
							sayac += 2;
						}
					}
				}
				else{
					// cerr << "flag1" << '\n';
					for(int j = 0;j<i;j++){
						while(cnt[j]--){
							if(arr[sayac] != -1)sayac += 2;
							arr[sayac] = j;
							sayac += 2;
						}
					}
				}
				break;
			}
		}
		arr[sayac] = maxi;
		cnt[maxi]--;
		int wtf = sayac-1;
		while(maxi >= 0 and cnt[maxi] == 0)maxi--;
		if(maxi != -1){
			sayac = 0;
			while(cnt[maxi]--){
				if(arr[sayac] != -1)sayac += 2;
				if(sayac >= wtf)arr.push_front(maxi);
				else arr[sayac] = maxi;
				
				sayac += 2;
			}
		}
		for(int i = 0;i<sz(arr);i++){
			if(arr[i] != -1){
				cout << arr[i]+1;
			}
		}
		cout << endl;
	}
	else {
		dfs(sum);
		assert(sz(pai.second) == sum);
		cout << pai.second << endl;	
	}
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

• Subtask 1: 13 / 13
• Subtask 2: 14 / 14
• Subtask 3: 0 / 29
• Subtask 4: 0 / 44