QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#837707#3074. Express As The SumwtcWA 22ms5568kbC++141.2kb2024-12-30 11:59:072024-12-30 11:59:08

Judging History

This is the latest submission verdict.

  • [2024-12-30 11:59:08]
  • Judged
  • Verdict: WA
  • Time: 22ms
  • Memory: 5568kb
  • [2024-12-30 11:59:07]
  • Submitted

answer

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=(l);i<=(r);++i)
#define fd(i,l,r) for(int i=(l);i>=(r);--i)
#define fu(i,l,r) for(int i=(l);i<(r);++i)
#define ll long long
using namespace std;
void out(int x){if(x>9)out(x/10);putchar(48+x%10);}
const int N=45007;
int n,bz[N],tot,p[N],b[N],c[N],o,pd;
vector<int>d;
void init(int n)
{
	fo(i,2,n)
	{
		if(!bz[i])
		{
			p[++tot]=i;
			for(int j=i+i;j<=n;j+=i) bz[j]=1;
		}
	}
}
void pt(int n,int l,int r)
{
	out(n);
	fo(i,l,r) putchar(' '),putchar(i==l?'=':'+'),putchar(' '),out(i);
	putchar('\n');
}
void dfs(int x,int y)
{
	if(pd) return;
	if(x==o+1){d.push_back(y);return;}
	fu(i,0,c[x]) dfs(x+1,y),y*=b[x];
	dfs(x+1,y);
}
void work()
{
	scanf("%d",&n);n*=2;
	int m=n;o=0;pd=0;
	for(int i=1;i<=tot&&p[i]*p[i]<=m;++i)
	{
		if(m%p[i]==0)
		{
			m/=p[i];b[++o]=p[i];c[o]=1;
			while(m%p[i]==0) m/=p[i],c[o]++;
		}
	}
	if(m>1) b[++o]=m,c[o]=1;
	dfs(1,1);
	for(int y:d)
	{
		int z=n/y;
		if(y==1||!((y&1)^(z&1))) continue;
		if(z<y) continue;
		pt(n>>1,(z-y+1)>>1,(z+y-1)>>1);
		return;
	}
	if(!pd) printf("IMPOSSIBLE\n");
}
int main()
{
	init(45000);
	int T;scanf("%d",&T);
	while(T--) work();
}

詳細信息

Test #1:

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

input:

3
8
10
24

output:

IMPOSSIBLE
10 = 1 + 2 + 3 + 4
24 = 7 + 8 + 9

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 22ms
memory: 5568kb

input:

10866
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...

output:

IMPOSSIBLE
IMPOSSIBLE
3 = 1 + 2
IMPOSSIBLE
5 = 2 + 3
6 = 1 + 2 + 3
7 = 3 + 4
IMPOSSIBLE
9 = 4 + 5
10 = 1 + 2 + 3 + 4
11 = 5 + 6
12 = 3 + 4 + 5
13 = 6 + 7
14 = 2 + 3 + 4 + 5
15 = 7 + 8
16 = 4 + 5 + 6
17 = 8 + 9
18 = 3 + 4 + 5 + 6
19 = 9 + 10
20 = 2 + 3 + 4 + 5 + 6
21 = 10 + 11
22 = 4 + 5 + 6 + 7
23 =...

result:

wrong answer 16th lines differ - expected: 'IMPOSSIBLE', found: '16 = 4 + 5 + 6'