QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#239337#7688. Alea Iacta Estucup-team191#WA 115ms27628kbC++142.1kb2023-11-04 20:10:252023-11-04 20:10:25

Judging History

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

  • [2023-11-04 20:10:25]
  • 评测
  • 测评结果:WA
  • 用时:115ms
  • 内存:27628kb
  • [2023-11-04 20:10:25]
  • 提交

answer

#include <bits/stdc++.h>
#define pb push_back
#define x first
#define y second

#define int long long

using namespace std;
using vi=vector<int>;

typedef long long ll;

const int N = 3e6 + 500;

int tmp[N], odg[N], cnt[N], svi[N], out = 0, in = 0;

vi mul(vi a,vi b)
{
	vi c;
	for (auto x: a) for (auto y: b) c.pb(x+y);
	return c;
}

vi getvec(int cn,int x)
{
	vi v;
	for (int i=0;i<cn;++i) v.pb(i*x);
	return v;
}

pair<vi,vi> decomp(int n,int a)
{
	assert(n%a==0);
	return {getvec(a,1),getvec(n/a,a)};
}

void solve(){
	int n, m; cin >> n >> m;
	if(n < m) swap(n, m);
	ll fak = (ll)n * m;
	ll poc = sqrt(fak) + 1;
	vi a1,a2;
	bool nad=0;
	if (n==m)
	{
		ll u=sqrt(n)+1;
		while (u*u>n) --u;
		if (u*u==n)
		{
			auto r1=decomp(n,u);
			a1=mul(r1.x,r1.x);
			a2=mul(r1.y,r1.y);
			nad=1;
		}
	}
	while (poc * poc > fak) poc--;
	for(ll i = poc;i >= 1;i--) {
		if (nad) break;
		if(fak % i == 0 && i != m && i + fak / i < (ll)n + 2 * m) {
			ll u=i,v=fak/i;
			ll u1=__gcd(u,n),u2=u/u1;
			ll v1=n/u1,v2=m/u2;
			assert(u1*v1==n);
			assert(u2*v2==m);
			assert(u1*u2==u);
			assert(v1*v2==v);
			auto r1=decomp(n,u1),r2=decomp(m,u2);
			a1=mul(r1.x,r2.x);
			a2=mul(r1.y,r2.y);
			nad=1;
			break;
		}
		if (fak%i==0 && i==m && i!=n && __gcd(n,m)>1)
		{
			ll u=__gcd(n,m);
			auto r1=decomp(n,u),r2=decomp(m,m/u);
			a1=mul(r1.x,r2.x);
			a2=mul(r1.y,r2.y);
			nad=1;
			break;
		}
		
	}
	if (!nad)
	{
		for (int i=0;i<n;++i) a1.pb(i);
		for (int i=0;i<m;++i) a2.pb(i),a2.pb(i);
		nad=1;
	}
	int f1=a1.size(),f2=a2.size();
	//cout << n << " " << m << "\n";
	
	cout<<f1<<"\n";
	for (auto x: a1) cout<<x+1<<' ';
	cout<<"\n";
	cout<<f2<<"\n";
	for (auto x: a2) cout<<x+1<<' ';
	cout<<"\n";
	
	out += f1 + f2; in += n;
	//cout << n << " " << m << " 		" << f1 << " " << f2 << endl;
	//if(f1 + f2 >= n + m) cout << "kurcina\n";
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	//cout << T << endl;
	for(;T--;) {
		//printf("T = %d\n", T);
		solve();
	}
	//cout << in << endl;
	//cout << out << endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3428kb

input:

3
2 8
1 9
2 9

output:

4
1 2 3 4 
4
1 2 5 6 
3
1 2 3 
3
1 4 7 
3
1 2 3 
6
1 2 4 5 7 8 

result:

ok Correct. (3 test cases)

Test #2:

score: 0
Accepted
time: 7ms
memory: 4428kb

input:

1
40013 40013

output:

40013
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #3:

score: 0
Accepted
time: 3ms
memory: 3696kb

input:

1
40013 1

output:

40013
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #4:

score: 0
Accepted
time: 3ms
memory: 3688kb

input:

1
2 40013

output:

40013
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #5:

score: 0
Accepted
time: 3ms
memory: 3724kb

input:

1
3 40013

output:

40013
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #6:

score: 0
Accepted
time: 3ms
memory: 3636kb

input:

1
4 40013

output:

40013
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 10...

result:

ok Correct. (1 test case)

Test #7:

score: 0
Accepted
time: 115ms
memory: 27628kb

input:

1
999983 999983

output:

999983
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #8:

score: 0
Accepted
time: 42ms
memory: 12368kb

input:

1
1 999983

output:

999983
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #9:

score: 0
Accepted
time: 42ms
memory: 11484kb

input:

1
2 999983

output:

999983
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #10:

score: 0
Accepted
time: 46ms
memory: 11956kb

input:

1
999983 3

output:

999983
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #11:

score: 0
Accepted
time: 51ms
memory: 13276kb

input:

1
999983 4

output:

999983
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

ok Correct. (1 test case)

Test #12:

score: 0
Accepted
time: 93ms
memory: 24564kb

input:

1
1000000 1000000

output:

1000000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 ...

result:

ok Correct. (1 test case)

Test #13:

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

input:

1
1000000 1

output:

1000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #14:

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

input:

1
1000000 2

output:

1250
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #15:

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

input:

1
3 1000000

output:

1600
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #16:

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

input:

1
4 1000000

output:

2000
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101...

result:

ok Correct. (1 test case)

Test #17:

score: -100
Wrong Answer
time: 66ms
memory: 23220kb

input:

1
988027 988027

output:

982081
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 1...

result:

wrong answer Jury has a better answer. (test case 1)