QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#69999 | #5236. Wersja dla profesjonalistów [A] | tygrysek | 0 | 2ms | 3460kb | C++17 | 4.3kb | 2023-01-04 03:01:41 | 2023-01-04 03:01:43 |
Judging History
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