QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#69999#5236. Wersja dla profesjonalistów [A]tygrysek0 2ms3460kbC++174.3kb2023-01-04 03:01:412023-01-04 03:01:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-01-04 03:01:43]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:3460kb
  • [2023-01-04 03:01:41]
  • 提交

answer

#include <stdio.h>
#include <time.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <map> 
#include <string>
#include <vector>  
#include <iostream> 
#include <sstream> 
#include <queue>
#include <algorithm>
#include <assert.h>


using namespace std;

#define ll long long
#define PB 		push_back
#define FOR(a,start,end) 	for(int a=int(start); a<int(end); a++)
#define INF 		INT_MAX
#define SORT(a) 	sort(a.begin(),a.end()) 
#define CL(a,x) 		memset(a,x,sizeof(a))
#define REP(a,x)	for(int a=0;a<x;a++)
#define REP1(a,x)	for(int a=1;a<=x;a++)
#define MP 		make_pair



typedef vector<ll>     vi;
typedef pair<ll, ll>     pii;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<vector<ll> > vvi;
typedef vector<vector<string> > vvs;
typedef vector<pair<string, string> > vss;
typedef pair<string, string> pss;
typedef pair<ll, pii> ppii;
typedef vector<ppii> vppii;
typedef vector<vector<pii> > vvii;
typedef vector<vvi> vvvi;


ll  n, k, q, d, r, g, b, z, p, a, c;
char zn;

string wa;
vi vk, va, vk1, vk2;
vector<bool> vb;
vi rozklad(ll n) {
	vi vk,vk1,vk2;
	vk.clear(); vk1.clear(); vk2.clear();
	vk1.push_back(1);
	
	while ((int)vk1.size()>0) {
		vk2.push_back(vk1.back());
		for (int i=0; i<(int)vk1.size(); i++) {
			if ((i > 0) && vk1[i] == vk1[i - 1])
				continue;
			for (int j = 0; j < 4; j++) {
				if (vk1[i] * va[j] > n)
					break;
				vk2.push_back(vk1[i] * va[j]);
				if (vk2.back() == n)
					break;
			}
			if (((int)vk2.size()>0)&&(vk2.back() == n))
				break;
		}
		vk1.swap(vk2);
		vk2.clear();
		SORT(vk1);
		if (((int)vk1.size()>0)&&(vk1.back() == n))
			break;
		if ((int)vk1.size() == 1)
			break;
	}
	
	k = vk1.back();
	
	int j = 0;
	ll m = k;
	while (m > 1) {
		while (m % va[j] == 0) {
			vk.push_back(va[j]);
			m /= va[j];
		}
		j++;
	}
	j = 1;
	while (j < (int)vk.size()) {
		if (vk[j] > 3)
			break;
		if (vk[j] * vk[j - 1] < 10) {
			vk[j - 1] *= vk[j];
			vk.erase(vk.begin() + j);
		}
		else
			j++;
	}
	vk.push_back(n - k);
	return vk;
}
vi rozklad2(ll n) {
	ll n0 = n;
	vi vk;
	vk.clear();
	ll k = 1;
	bool ok = true;
	while (ok) {
		ok = false;
		for (int a = 9; a >= 2; a--) {
			if (n%a == 0) {
				n /= a;
				vk.push_back(a);
				ok = true;
				break;
			}
		}
		if (!ok) {
			n--;
			ok = true;
		}
		if (n == 1)
			break;
	}
	for (int i = 0; i < vk.size(); i++)
		k *= vk[i];
	SORT(vk);
	int j = 1;
	while (j < (int)vk.size()) {
		if (vk[j] > 3)
			break;
		if (vk[j] * vk[j - 1] < 10) {
			vk[j - 1] *= vk[j];
			vk.erase(vk.begin() + j);
		}
		else
			j++;
	}
	SORT(vk);
	if ((int)vk.size() > 1) {
		int j = (int)vk.size() - 1;
		while (j > 0) {
			if (vk[j] == 9)
				continue;
			if ((k / vk[j]) * (vk[j] + 1) <= n0) {
				k /= vk[j];
				vk[j]++;
				k *= vk[j];
				break;
			}
		}
	}
	vk.push_back(n0 - k);
	return vk;
}

string multi(ll n, string w) {
	vi vk;
	
	string wy;
	wy.clear();
	
	if (n > 0) {
		if ((n <= 3) && ((int)w.size() == 1)) {
			for (int i = 0; i < n; i++)
				wy += w;
		}
		else if ((n <= 2) && ((int)w.size() == 2)) {
			for (int i = 0; i < n; i++)
				wy += w;
		}
		else {
			vk = rozklad2(n);
			for (int i = 0; i < (int)vk.size() - 1; i++) {
				wy += vk[i] + '0';
				wy += '[';
			}
			wy += w;
			string wk;
			wk.assign((int)vk.size() - 1, ']');
			wy += wk;
			if (vk.back() > 1)
				wy += multi(vk.back(), w);
			else if (vk.back() == 1)
				wy += w;
		}
	}
	return wy;
}
string build(ll n0) {
	string wy;
	wy.clear();
	if (n0 == 1)
		return "AE";
	else if (n0 % 2 == 0) {
		wy = build(n0 - 1);
		wy += multi(n0 - 1, "AC");
		wy += 'A';
		wy += multi(n0, "E");
	}
	else {
		wy += "2[";
		wy += build((n0 - 1) / 2);
		wy += ']';
		wy+= multi((n0 - 1) / 2, "AC");

		string wk = multi(((n0 - 1) / 2) - 1, "CE");
		wk += 'C';
		wk+= multi((n0 - 1) / 2, "A");
		wy += multi((n0 - 1) / 2, wk);
		wy += multi((n0 - 1) / 2, "E");
		wy += multi((n0 - 1) / 2, "AC");
		wy += 'A';
		wy += multi(n0, "E");
	}
	return wy;
}
int main() {
	//freopen("c:\\wojtek\\uva\\pa\\debug\\1.in", "rt", stdin);
	//d = 1000000007;

	//while (1) {
	va = { 2,3,5,7 }; 
	cin >> n ;
	wa = build(n);
	wa += multi(n, "C");
	cout << wa << endl;


	// }

	return 0;

}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Time Limit Exceeded

Test #1:

score: 1
Accepted
time: 0ms
memory: 3352kb

input:

1

output:

AEC

result:

ok correct (length = 3)

Test #2:

score: 0
Accepted
time: 2ms
memory: 3460kb

input:

2

output:

AEACAEECC

result:

ok correct (length = 13)

Test #3:

score: 0
Accepted
time: 2ms
memory: 3344kb

input:

4

output:

2[AE]ACCAEACAEEE3[AC]A4[E]4[C]

result:

ok correct (length = 30)

Test #4:

score: 0
Accepted
time: 1ms
memory: 3248kb

input:

5

output:

2[AEACAEE]ACAC2[CECAA]EEACACA5[E]5[C]

result:

ok correct (length = 43)

Test #5:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

6

output:

2[AEACAEE]ACAC2[CECAA]EEACACA5[E]5[AC]A6[E]6[C]

result:

ok correct (length = 53)

Test #6:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

7

output:

2[2[AE]ACCAEACAEEE]3[AC]3[CECECAAA]EEE3[AC]A7[E]7[C]

result:

ok correct (length = 53)

Test #7:

score: -1
Time Limit Exceeded

input:

10

output:


result:


Subtask #2:

score: 0
Time Limit Exceeded

Test #16:

score: 0
Time Limit Exceeded

input:

320

output:


result:


Subtask #3:

score: 0
Time Limit Exceeded

Test #28:

score: 0
Time Limit Exceeded

input:

1000000

output:


result:


Subtask #4:

score: 0
Time Limit Exceeded

Test #37:

score: 0
Time Limit Exceeded

input:

999999

output:


result:


Subtask #5:

score: 0
Time Limit Exceeded

Test #46:

score: 0
Time Limit Exceeded

input:

10000000000

output:


result:


Subtask #6:

score: 0
Time Limit Exceeded

Test #55:

score: 0
Time Limit Exceeded

input:

9999999999

output:


result:


Subtask #7:

score: 0
Time Limit Exceeded

Test #64:

score: 0
Time Limit Exceeded

input:

100000000000000

output:


result:


Subtask #8:

score: 0
Time Limit Exceeded

Test #84:

score: 0
Time Limit Exceeded

input:

99999999999999

output:


result:


Subtask #9:

score: 0
Time Limit Exceeded

Test #103:

score: 0
Time Limit Exceeded

input:

1000000000000000000

output:


result:


Subtask #10:

score: 0
Time Limit Exceeded

Test #128:

score: 0
Time Limit Exceeded

input:

999999999999999999

output:


result: