답안 #40453 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
40453	2018-02-01T16:37:04 Z	Pajaraja	Nice sequence (IZhO18_sequence)	C++14	76 / 100	614 ms	17264 KB

sequence

#include <bits/stdc++.h>
using namespace std;
vector<int> g[200007];
int pv[200007],deg[200007],parc[200007];
bool provera(int s,int n,int m)
{
	fill(deg,deg+s+1,0);
	for(int i=0;i<=s;i++) g[i].clear();
	for(int i=n;i<=s;i++) 
	{
	    g[i].push_back(i-n);
	    deg[i-n]++;
	}
	for(int i=m;i<=s;i++)
	{
		g[i-m].push_back(i);
		deg[i]++;
	}
	queue<int> q;
	for(int i=0;i<=s;i++) if(deg[i]==0) q.push(i);
	int cnt=0;
	while(!q.empty())
	{
		int u=q.front();
		pv[u]=cnt++;
		q.pop();
		for(int i=0;i<g[u].size();i++) 
		{
			deg[g[u][i]]--;
			if(deg[g[u][i]]==0) q.push(g[u][i]);
		}
	}
	if(cnt<=s) return false;
	return true;
}
int binarna(int l,int r,int n,int m)
{
	if(l==r) return l;
	int s=(l+r)/2;
	if(!provera(s,n,m)) return binarna(l,s,n,m);
	else return binarna(s+1,r,n,m);
}
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		int n,m;
		scanf("%d%d",&n,&m);
		int x=binarna(0,200006,n,m);
		printf("%d\n",x-1);
		provera(x-1,n,m);
		for(int i=1;i<x;i++) printf("%d ",pv[i]-pv[i-1]);
		printf("\n");
	}
}

Compilation message

sequence.cpp: In function 'bool provera(int, int, int)':
sequence.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i=0;i<g[u].size();i++) 
                ^
sequence.cpp: In function 'int main()':
sequence.cpp:46:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&t);
                ^
sequence.cpp:50:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&n,&m);
                      ^

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	8568 KB	Ok
2	Correct	56 ms	8568 KB	Ok
3	Correct	53 ms	8596 KB	Ok
4	Correct	56 ms	8776 KB	Ok
5	Correct	53 ms	8996 KB	Ok
6	Correct	60 ms	8996 KB	Ok
7	Correct	53 ms	8996 KB	Ok
8	Correct	53 ms	8996 KB	Ok
9	Correct	53 ms	8996 KB	Ok
10	Correct	53 ms	8996 KB	Ok
11	Correct	53 ms	8996 KB	Ok
12	Correct	53 ms	8996 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	8996 KB	Ok
2	Correct	53 ms	8996 KB	Ok
3	Correct	53 ms	8996 KB	Ok
4	Correct	53 ms	8996 KB	Ok
5	Correct	55 ms	8996 KB	Ok
6	Correct	58 ms	8996 KB	Ok
7	Correct	77 ms	9196 KB	Ok
8	Correct	63 ms	9196 KB	Ok
9	Correct	82 ms	9228 KB	Ok
10	Correct	69 ms	9228 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	28 ms	9228 KB	Ok
2	Correct	54 ms	9228 KB	Ok
3	Correct	55 ms	9228 KB	Ok
4	Correct	67 ms	9228 KB	Ok
5	Correct	54 ms	9228 KB	Ok
6	Correct	53 ms	9228 KB	Ok
7	Correct	56 ms	9228 KB	Ok
8	Correct	53 ms	9228 KB	Ok
9	Correct	53 ms	9228 KB	Ok
10	Correct	52 ms	9228 KB	Ok
11	Correct	55 ms	9228 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	53 ms	9228 KB	Ok
2	Correct	54 ms	9228 KB	Ok
3	Correct	52 ms	9228 KB	Ok
4	Correct	66 ms	9228 KB	Ok
5	Correct	54 ms	9228 KB	Ok
6	Correct	370 ms	15244 KB	Ok
7	Correct	333 ms	15244 KB	Ok
8	Correct	614 ms	17264 KB	Ok
9	Correct	450 ms	17264 KB	Ok
10	Correct	283 ms	17264 KB	Ok
11	Correct	441 ms	17264 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	8568 KB	Ok
2	Correct	56 ms	8568 KB	Ok
3	Correct	53 ms	8596 KB	Ok
4	Correct	56 ms	8776 KB	Ok
5	Correct	53 ms	8996 KB	Ok
6	Correct	60 ms	8996 KB	Ok
7	Correct	53 ms	8996 KB	Ok
8	Correct	53 ms	8996 KB	Ok
9	Correct	53 ms	8996 KB	Ok
10	Correct	53 ms	8996 KB	Ok
11	Correct	53 ms	8996 KB	Ok
12	Correct	53 ms	8996 KB	Ok
13	Correct	28 ms	9228 KB	Ok
14	Correct	54 ms	9228 KB	Ok
15	Correct	55 ms	9228 KB	Ok
16	Correct	67 ms	9228 KB	Ok
17	Correct	54 ms	9228 KB	Ok
18	Correct	53 ms	9228 KB	Ok
19	Correct	56 ms	9228 KB	Ok
20	Correct	53 ms	9228 KB	Ok
21	Correct	53 ms	9228 KB	Ok
22	Correct	52 ms	9228 KB	Ok
23	Correct	55 ms	9228 KB	Ok
24	Correct	56 ms	17264 KB	Ok
25	Correct	59 ms	17264 KB	Ok
26	Correct	56 ms	17264 KB	Ok
27	Correct	56 ms	17264 KB	Ok
28	Correct	55 ms	17264 KB	Ok
29	Correct	55 ms	17264 KB	Ok
30	Correct	56 ms	17264 KB	Ok
31	Correct	56 ms	17264 KB	Ok
32	Correct	56 ms	17264 KB	Ok
33	Correct	57 ms	17264 KB	Ok
34	Correct	62 ms	17264 KB	Ok
35	Correct	63 ms	17264 KB	Ok
36	Correct	62 ms	17264 KB	Ok
37	Correct	63 ms	17264 KB	Ok
38	Correct	63 ms	17264 KB	Ok
39	Correct	61 ms	17264 KB	Ok
40	Correct	61 ms	17264 KB	Ok
41	Correct	61 ms	17264 KB	Ok
42	Correct	62 ms	17264 KB	Ok
43	Correct	62 ms	17264 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	8568 KB	Ok
2	Correct	56 ms	8568 KB	Ok
3	Correct	53 ms	8596 KB	Ok
4	Correct	56 ms	8776 KB	Ok
5	Correct	53 ms	8996 KB	Ok
6	Correct	60 ms	8996 KB	Ok
7	Correct	53 ms	8996 KB	Ok
8	Correct	53 ms	8996 KB	Ok
9	Correct	53 ms	8996 KB	Ok
10	Correct	53 ms	8996 KB	Ok
11	Correct	53 ms	8996 KB	Ok
12	Correct	53 ms	8996 KB	Ok
13	Correct	53 ms	8996 KB	Ok
14	Correct	53 ms	8996 KB	Ok
15	Correct	53 ms	8996 KB	Ok
16	Correct	53 ms	8996 KB	Ok
17	Correct	55 ms	8996 KB	Ok
18	Correct	58 ms	8996 KB	Ok
19	Correct	77 ms	9196 KB	Ok
20	Correct	63 ms	9196 KB	Ok
21	Correct	82 ms	9228 KB	Ok
22	Correct	69 ms	9228 KB	Ok
23	Correct	28 ms	9228 KB	Ok
24	Correct	54 ms	9228 KB	Ok
25	Correct	55 ms	9228 KB	Ok
26	Correct	67 ms	9228 KB	Ok
27	Correct	54 ms	9228 KB	Ok
28	Correct	53 ms	9228 KB	Ok
29	Correct	56 ms	9228 KB	Ok
30	Correct	53 ms	9228 KB	Ok
31	Correct	53 ms	9228 KB	Ok
32	Correct	52 ms	9228 KB	Ok
33	Correct	55 ms	9228 KB	Ok
34	Correct	56 ms	17264 KB	Ok
35	Correct	59 ms	17264 KB	Ok
36	Correct	56 ms	17264 KB	Ok
37	Correct	56 ms	17264 KB	Ok
38	Correct	55 ms	17264 KB	Ok
39	Correct	55 ms	17264 KB	Ok
40	Correct	56 ms	17264 KB	Ok
41	Correct	56 ms	17264 KB	Ok
42	Correct	56 ms	17264 KB	Ok
43	Correct	57 ms	17264 KB	Ok
44	Correct	62 ms	17264 KB	Ok
45	Correct	63 ms	17264 KB	Ok
46	Correct	62 ms	17264 KB	Ok
47	Correct	63 ms	17264 KB	Ok
48	Correct	63 ms	17264 KB	Ok
49	Correct	61 ms	17264 KB	Ok
50	Correct	61 ms	17264 KB	Ok
51	Correct	61 ms	17264 KB	Ok
52	Correct	62 ms	17264 KB	Ok
53	Correct	62 ms	17264 KB	Ok
54	Correct	261 ms	17264 KB	Ok
55	Correct	321 ms	17264 KB	Ok
56	Correct	311 ms	17264 KB	Ok
57	Correct	232 ms	17264 KB	Ok
58	Correct	314 ms	17264 KB	Ok
59	Correct	272 ms	17264 KB	Ok
60	Correct	225 ms	17264 KB	Ok
61	Correct	241 ms	17264 KB	Ok
62	Correct	326 ms	17264 KB	Ok
63	Correct	302 ms	17264 KB	Ok
64	Correct	298 ms	17264 KB	Ok
65	Correct	302 ms	17264 KB	Ok
66	Correct	282 ms	17264 KB	Ok
67	Correct	217 ms	17264 KB	Ok
68	Correct	264 ms	17264 KB	Ok
69	Correct	523 ms	17264 KB	Ok
70	Correct	567 ms	17264 KB	Ok
71	Correct	502 ms	17264 KB	Ok
72	Correct	574 ms	17264 KB	Ok
73	Correct	520 ms	17264 KB	Ok
74	Correct	512 ms	17264 KB	Ok
75	Correct	515 ms	17264 KB	Ok
76	Correct	568 ms	17264 KB	Ok
77	Correct	477 ms	17264 KB	Ok
78	Correct	512 ms	17264 KB	Ok
79	Correct	490 ms	17264 KB	Ok
80	Correct	511 ms	17264 KB	Ok
81	Correct	518 ms	17264 KB	Ok
82	Correct	517 ms	17264 KB	Ok
83	Correct	488 ms	17264 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	54 ms	8568 KB	Ok
2	Correct	56 ms	8568 KB	Ok
3	Correct	53 ms	8596 KB	Ok
4	Correct	56 ms	8776 KB	Ok
5	Correct	53 ms	8996 KB	Ok
6	Correct	60 ms	8996 KB	Ok
7	Correct	53 ms	8996 KB	Ok
8	Correct	53 ms	8996 KB	Ok
9	Correct	53 ms	8996 KB	Ok
10	Correct	53 ms	8996 KB	Ok
11	Correct	53 ms	8996 KB	Ok
12	Correct	53 ms	8996 KB	Ok
13	Correct	53 ms	8996 KB	Ok
14	Correct	53 ms	8996 KB	Ok
15	Correct	53 ms	8996 KB	Ok
16	Correct	53 ms	8996 KB	Ok
17	Correct	55 ms	8996 KB	Ok
18	Correct	58 ms	8996 KB	Ok
19	Correct	77 ms	9196 KB	Ok
20	Correct	63 ms	9196 KB	Ok
21	Correct	82 ms	9228 KB	Ok
22	Correct	69 ms	9228 KB	Ok
23	Correct	28 ms	9228 KB	Ok
24	Correct	54 ms	9228 KB	Ok
25	Correct	55 ms	9228 KB	Ok
26	Correct	67 ms	9228 KB	Ok
27	Correct	54 ms	9228 KB	Ok
28	Correct	53 ms	9228 KB	Ok
29	Correct	56 ms	9228 KB	Ok
30	Correct	53 ms	9228 KB	Ok
31	Correct	53 ms	9228 KB	Ok
32	Correct	52 ms	9228 KB	Ok
33	Correct	55 ms	9228 KB	Ok
34	Correct	53 ms	9228 KB	Ok
35	Correct	54 ms	9228 KB	Ok
36	Correct	52 ms	9228 KB	Ok
37	Correct	66 ms	9228 KB	Ok
38	Correct	54 ms	9228 KB	Ok
39	Correct	370 ms	15244 KB	Ok
40	Correct	333 ms	15244 KB	Ok
41	Correct	614 ms	17264 KB	Ok
42	Correct	450 ms	17264 KB	Ok
43	Correct	283 ms	17264 KB	Ok
44	Correct	441 ms	17264 KB	Ok
45	Correct	56 ms	17264 KB	Ok
46	Correct	59 ms	17264 KB	Ok
47	Correct	56 ms	17264 KB	Ok
48	Correct	56 ms	17264 KB	Ok
49	Correct	55 ms	17264 KB	Ok
50	Correct	55 ms	17264 KB	Ok
51	Correct	56 ms	17264 KB	Ok
52	Correct	56 ms	17264 KB	Ok
53	Correct	56 ms	17264 KB	Ok
54	Correct	57 ms	17264 KB	Ok
55	Correct	62 ms	17264 KB	Ok
56	Correct	63 ms	17264 KB	Ok
57	Correct	62 ms	17264 KB	Ok
58	Correct	63 ms	17264 KB	Ok
59	Correct	63 ms	17264 KB	Ok
60	Correct	61 ms	17264 KB	Ok
61	Correct	61 ms	17264 KB	Ok
62	Correct	61 ms	17264 KB	Ok
63	Correct	62 ms	17264 KB	Ok
64	Correct	62 ms	17264 KB	Ok
65	Correct	261 ms	17264 KB	Ok
66	Correct	321 ms	17264 KB	Ok
67	Correct	311 ms	17264 KB	Ok
68	Correct	232 ms	17264 KB	Ok
69	Correct	314 ms	17264 KB	Ok
70	Correct	272 ms	17264 KB	Ok
71	Correct	225 ms	17264 KB	Ok
72	Correct	241 ms	17264 KB	Ok
73	Correct	326 ms	17264 KB	Ok
74	Correct	302 ms	17264 KB	Ok
75	Correct	298 ms	17264 KB	Ok
76	Correct	302 ms	17264 KB	Ok
77	Correct	282 ms	17264 KB	Ok
78	Correct	217 ms	17264 KB	Ok
79	Correct	264 ms	17264 KB	Ok
80	Correct	523 ms	17264 KB	Ok
81	Correct	567 ms	17264 KB	Ok
82	Correct	502 ms	17264 KB	Ok
83	Correct	574 ms	17264 KB	Ok
84	Correct	520 ms	17264 KB	Ok
85	Correct	512 ms	17264 KB	Ok
86	Correct	515 ms	17264 KB	Ok
87	Correct	568 ms	17264 KB	Ok
88	Correct	477 ms	17264 KB	Ok
89	Correct	512 ms	17264 KB	Ok
90	Correct	490 ms	17264 KB	Ok
91	Correct	511 ms	17264 KB	Ok
92	Correct	518 ms	17264 KB	Ok
93	Correct	517 ms	17264 KB	Ok
94	Correct	488 ms	17264 KB	Ok
95	Incorrect	588 ms	17264 KB	Jury has the better answer : jans = 239234, pans = 200005
96	Halted	0 ms	0 KB	-

답안 #40453

Compilation message

Subtask #1 6.0 / 6.0

Subtask #2 9.0 / 9.0

Subtask #3 14.0 / 14.0

Subtask #4 15.0 / 15.0

Subtask #5 14.0 / 14.0

Subtask #6 18.0 / 18.0

Subtask #7 0 / 24.0

Subtask #1
6.0 / 6.0

Subtask #2
9.0 / 9.0

Subtask #3
14.0 / 14.0

Subtask #4
15.0 / 15.0

Subtask #5
14.0 / 14.0

Subtask #6
18.0 / 18.0

Subtask #7
0 / 24.0