QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#420862#8678. A Recurring ProblembulijiojiodibuliduoWA 249ms15916kbC++172.8kb2024-05-25 01:24:242024-05-25 01:24:24

Judging History

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

  • [2024-05-25 01:24:24]
  • 评测
  • 测评结果:WA
  • 用时:249ms
  • 内存:15916kb
  • [2024-05-25 01:24:24]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef long long ll;
typedef vector<ll> VI;
typedef basic_string<int> BI;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

//ll f[1111],ret,g[30][30][1111],tg[30][1111];
map<pair<VI,VI>,map<ll,ll>> hs;
map<ll,ll> count(VI s,VI coef) {
	map<ll,ll> v;
	if (s[0]==0) {
		bool z=1;
		for (auto x:s) z&=(x==0);
		if (z) v[0]=1;
		return v;
	}
	if (hs.count(mp(s,coef))) return hs[mp(s,coef)];
	if (SZ(s)>=2) {
		VI ss=s,cc=coef;
		ss.pop_back(); cc.pop_back();
		if (count(ss,cc).empty()) return v;
	}
	for (int j=1;j<=s[0];j++) for (int k=1;k*j<=s[0];k++) {
		VI ncoef=coef,ns=s; ncoef.insert(ncoef.begin(),k);
		bool val=1;
		rep(l,0,SZ(s)) {
			ns[l]=ns[l]-j*ncoef[l];
			if (ns[l]<0) { val=0; break; }
		}
		ncoef.pop_back();
		if (val) {
			auto d=count(ns,ncoef);
			for (auto [key,val]:d) v[key+j*coef.back()]+=val;
		}
	}
	return hs[mp(s,coef)]=v;
}
vector<pair<VI,VI>> ret;
void dfs(VI s,VI coef,VI p1,VI p2) {
	if (s[0]==0) {
		bool z=1;
		for (auto x:s) z&=(x==0);
		if (z) {
			reverse(all(p1));
			reverse(all(p2));
			ret.pb(mp(p1,p2));
		}
	}
	if (SZ(s)>=2) {
		VI ss=s,cc=coef;
		ss.pop_back(); cc.pop_back();
		if (count(ss,cc).empty()) return;
	} 
	for (int j=1;j<=s[0];j++) for (int k=1;k*j<=s[0];k++) {
		VI ncoef=coef,ns=s; ncoef.insert(ncoef.begin(),k);
		bool val=1;
		rep(l,0,SZ(s)) {
			ns[l]=ns[l]-j*ncoef[l];
			if (ns[l]<0) { val=0; break; }
		}
		VI q1=p1,q2=p2; q1.pb(j); q2.pb(k);
		ncoef.pop_back();
		if (val) dfs(ns,ncoef,q1,q2);
	}
}
int K;
VI seq;
int main() {
	scanf("%d",&K);
	rep(i,1,25) {
		auto d=count(VI{i},VI{i});
		ll z=0;
		for (auto [key,val]:d) {
			z+=val;
		}
		if (K>z) {
			K-=z;
		} else {
			seq.pb(i);
			break;
		}
	}
	ll v=0;
	rep(rd,1,10) {
		auto d=count(seq,seq);
		for (auto [key,val]:d) {
			if (K>val) {
				K-=val;
			} else {
				seq.pb(key);
				fprintf(stderr,"%lld %lld\n",key,val);
				v=val;
				break;
			}
		}
	}
	dfs(seq,seq,VI{},VI{});
	assert(SZ(ret)==v);
	sort(all(ret));
	fprintf(stderr,"!! %d\n",K);
	auto [p1,p2]=ret[K-1];
	printf("%d\n",SZ(p1));
	reverse(all(p1));
	for (auto x:p1) printf("%lld ",x); puts("");
	for (auto x:p2) printf("%lld ",x); puts("");
	for (auto x:seq) printf("%lld ",x); puts("");
}

詳細信息

Test #1:

score: 100
Accepted
time: 249ms
memory: 15916kb

input:

810832525

output:

1
23 
1 
23 529 12167 279841 6436343 148035889 3404825447 78310985281 1801152661463 41426511213649 

result:

ok 4 lines

Test #2:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

1

output:

1
1 
1 
1 1 1 1 1 1 1 1 1 1 

result:

ok 4 lines

Test #3:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

2

output:

1
1 
2 
2 2 2 2 2 2 2 2 2 2 

result:

ok 4 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 4096kb

input:

4

output:

1
2 
1 
2 4 8 16 32 64 128 256 512 1024 

result:

ok 4 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 4108kb

input:

5

output:

1
1 
3 
3 3 3 3 3 3 3 3 3 3 

result:

ok 4 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

6

output:

2
1 1 
2 1 
3 4 7 11 18 29 47 76 123 199 

result:

ok 4 lines

Test #7:

score: 0
Accepted
time: 0ms
memory: 3816kb

input:

7

output:

2
1 1 
1 2 
3 5 8 13 21 34 55 89 144 233 

result:

ok 4 lines

Test #8:

score: 0
Accepted
time: 0ms
memory: 4104kb

input:

8

output:

3
1 1 1 
1 1 1 
3 5 9 17 31 57 105 193 355 653 

result:

ok 4 lines

Test #9:

score: -100
Wrong Answer
time: 0ms
memory: 3884kb

input:

9

output:

2
1 2 
1 1 
3 5 11 21 43 85 171 341 683 1365 

result:

wrong answer 2nd lines differ - expected: '2 1', found: '1 2 '