답안 #40455 :: oj.uz

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

sequence

#include <bits/stdc++.h>
using namespace std;
vector<int> g[400007];
int pv[400007],deg[400007],parc[400007];
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(fmax(m,n)-1,m+n+5,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	8 ms	9720 KB	Ok
2	Correct	8 ms	9824 KB	Ok
3	Correct	10 ms	9840 KB	Ok
4	Correct	11 ms	9840 KB	Ok
5	Correct	8 ms	9840 KB	Ok
6	Correct	8 ms	9840 KB	Ok
7	Correct	8 ms	9856 KB	Ok
8	Correct	11 ms	9920 KB	Ok
9	Correct	8 ms	9920 KB	Ok
10	Correct	8 ms	9920 KB	Ok
11	Correct	8 ms	9944 KB	Ok
12	Correct	8 ms	9964 KB	Ok

Subtask #2
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	9964 KB	Ok
2	Correct	8 ms	9964 KB	Ok
3	Correct	8 ms	9964 KB	Ok
4	Correct	9 ms	9964 KB	Ok
5	Correct	9 ms	9964 KB	Ok
6	Correct	12 ms	10092 KB	Ok
7	Correct	24 ms	10604 KB	Ok
8	Correct	15 ms	10604 KB	Ok
9	Correct	28 ms	10764 KB	Ok
10	Correct	18 ms	10764 KB	Ok

Subtask #3
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	10764 KB	Ok
2	Correct	8 ms	10764 KB	Ok
3	Correct	8 ms	10764 KB	Ok
4	Correct	9 ms	10764 KB	Ok
5	Correct	11 ms	10764 KB	Ok
6	Correct	9 ms	10764 KB	Ok
7	Correct	9 ms	10764 KB	Ok
8	Correct	8 ms	10764 KB	Ok
9	Correct	8 ms	10764 KB	Ok
10	Correct	11 ms	10764 KB	Ok
11	Correct	9 ms	10764 KB	Ok

Subtask #4
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	10 ms	10764 KB	Ok
2	Correct	8 ms	10764 KB	Ok
3	Correct	8 ms	10764 KB	Ok
4	Correct	9 ms	10764 KB	Ok
5	Correct	8 ms	10764 KB	Ok
6	Correct	336 ms	19284 KB	Ok
7	Correct	324 ms	20048 KB	Ok
8	Correct	610 ms	21996 KB	Ok
9	Correct	436 ms	21996 KB	Ok
10	Correct	267 ms	21996 KB	Ok
11	Correct	453 ms	21996 KB	Ok

Subtask #5
14.0 / 14.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	9720 KB	Ok
2	Correct	8 ms	9824 KB	Ok
3	Correct	10 ms	9840 KB	Ok
4	Correct	11 ms	9840 KB	Ok
5	Correct	8 ms	9840 KB	Ok
6	Correct	8 ms	9840 KB	Ok
7	Correct	8 ms	9856 KB	Ok
8	Correct	11 ms	9920 KB	Ok
9	Correct	8 ms	9920 KB	Ok
10	Correct	8 ms	9920 KB	Ok
11	Correct	8 ms	9944 KB	Ok
12	Correct	8 ms	9964 KB	Ok
13	Correct	8 ms	10764 KB	Ok
14	Correct	8 ms	10764 KB	Ok
15	Correct	8 ms	10764 KB	Ok
16	Correct	9 ms	10764 KB	Ok
17	Correct	11 ms	10764 KB	Ok
18	Correct	9 ms	10764 KB	Ok
19	Correct	9 ms	10764 KB	Ok
20	Correct	8 ms	10764 KB	Ok
21	Correct	8 ms	10764 KB	Ok
22	Correct	11 ms	10764 KB	Ok
23	Correct	9 ms	10764 KB	Ok
24	Correct	13 ms	21996 KB	Ok
25	Correct	15 ms	21996 KB	Ok
26	Correct	14 ms	21996 KB	Ok
27	Correct	13 ms	21996 KB	Ok
28	Correct	12 ms	21996 KB	Ok
29	Correct	12 ms	21996 KB	Ok
30	Correct	17 ms	21996 KB	Ok
31	Correct	19 ms	21996 KB	Ok
32	Correct	19 ms	21996 KB	Ok
33	Correct	13 ms	21996 KB	Ok
34	Correct	25 ms	21996 KB	Ok
35	Correct	21 ms	21996 KB	Ok
36	Correct	28 ms	21996 KB	Ok
37	Correct	19 ms	21996 KB	Ok
38	Correct	21 ms	21996 KB	Ok
39	Correct	20 ms	21996 KB	Ok
40	Correct	21 ms	21996 KB	Ok
41	Correct	19 ms	21996 KB	Ok
42	Correct	19 ms	21996 KB	Ok
43	Correct	22 ms	21996 KB	Ok

Subtask #6
18.0 / 18.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	9720 KB	Ok
2	Correct	8 ms	9824 KB	Ok
3	Correct	10 ms	9840 KB	Ok
4	Correct	11 ms	9840 KB	Ok
5	Correct	8 ms	9840 KB	Ok
6	Correct	8 ms	9840 KB	Ok
7	Correct	8 ms	9856 KB	Ok
8	Correct	11 ms	9920 KB	Ok
9	Correct	8 ms	9920 KB	Ok
10	Correct	8 ms	9920 KB	Ok
11	Correct	8 ms	9944 KB	Ok
12	Correct	8 ms	9964 KB	Ok
13	Correct	8 ms	9964 KB	Ok
14	Correct	8 ms	9964 KB	Ok
15	Correct	8 ms	9964 KB	Ok
16	Correct	9 ms	9964 KB	Ok
17	Correct	9 ms	9964 KB	Ok
18	Correct	12 ms	10092 KB	Ok
19	Correct	24 ms	10604 KB	Ok
20	Correct	15 ms	10604 KB	Ok
21	Correct	28 ms	10764 KB	Ok
22	Correct	18 ms	10764 KB	Ok
23	Correct	8 ms	10764 KB	Ok
24	Correct	8 ms	10764 KB	Ok
25	Correct	8 ms	10764 KB	Ok
26	Correct	9 ms	10764 KB	Ok
27	Correct	11 ms	10764 KB	Ok
28	Correct	9 ms	10764 KB	Ok
29	Correct	9 ms	10764 KB	Ok
30	Correct	8 ms	10764 KB	Ok
31	Correct	8 ms	10764 KB	Ok
32	Correct	11 ms	10764 KB	Ok
33	Correct	9 ms	10764 KB	Ok
34	Correct	13 ms	21996 KB	Ok
35	Correct	15 ms	21996 KB	Ok
36	Correct	14 ms	21996 KB	Ok
37	Correct	13 ms	21996 KB	Ok
38	Correct	12 ms	21996 KB	Ok
39	Correct	12 ms	21996 KB	Ok
40	Correct	17 ms	21996 KB	Ok
41	Correct	19 ms	21996 KB	Ok
42	Correct	19 ms	21996 KB	Ok
43	Correct	13 ms	21996 KB	Ok
44	Correct	25 ms	21996 KB	Ok
45	Correct	21 ms	21996 KB	Ok
46	Correct	28 ms	21996 KB	Ok
47	Correct	19 ms	21996 KB	Ok
48	Correct	21 ms	21996 KB	Ok
49	Correct	20 ms	21996 KB	Ok
50	Correct	21 ms	21996 KB	Ok
51	Correct	19 ms	21996 KB	Ok
52	Correct	19 ms	21996 KB	Ok
53	Correct	22 ms	21996 KB	Ok
54	Correct	248 ms	21996 KB	Ok
55	Correct	288 ms	21996 KB	Ok
56	Correct	299 ms	21996 KB	Ok
57	Correct	214 ms	21996 KB	Ok
58	Correct	272 ms	21996 KB	Ok
59	Correct	262 ms	21996 KB	Ok
60	Correct	212 ms	21996 KB	Ok
61	Correct	210 ms	21996 KB	Ok
62	Correct	308 ms	21996 KB	Ok
63	Correct	219 ms	21996 KB	Ok
64	Correct	289 ms	21996 KB	Ok
65	Correct	273 ms	21996 KB	Ok
66	Correct	243 ms	21996 KB	Ok
67	Correct	244 ms	21996 KB	Ok
68	Correct	268 ms	21996 KB	Ok
69	Correct	562 ms	21996 KB	Ok
70	Correct	591 ms	21996 KB	Ok
71	Correct	549 ms	21996 KB	Ok
72	Correct	588 ms	21996 KB	Ok
73	Correct	522 ms	21996 KB	Ok
74	Correct	499 ms	21996 KB	Ok
75	Correct	534 ms	21996 KB	Ok
76	Correct	613 ms	21996 KB	Ok
77	Correct	517 ms	21996 KB	Ok
78	Correct	547 ms	21996 KB	Ok
79	Correct	572 ms	21996 KB	Ok
80	Correct	520 ms	21996 KB	Ok
81	Correct	530 ms	21996 KB	Ok
82	Correct	522 ms	21996 KB	Ok
83	Correct	516 ms	21996 KB	Ok

Subtask #7
0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	8 ms	9720 KB	Ok
2	Correct	8 ms	9824 KB	Ok
3	Correct	10 ms	9840 KB	Ok
4	Correct	11 ms	9840 KB	Ok
5	Correct	8 ms	9840 KB	Ok
6	Correct	8 ms	9840 KB	Ok
7	Correct	8 ms	9856 KB	Ok
8	Correct	11 ms	9920 KB	Ok
9	Correct	8 ms	9920 KB	Ok
10	Correct	8 ms	9920 KB	Ok
11	Correct	8 ms	9944 KB	Ok
12	Correct	8 ms	9964 KB	Ok
13	Correct	8 ms	9964 KB	Ok
14	Correct	8 ms	9964 KB	Ok
15	Correct	8 ms	9964 KB	Ok
16	Correct	9 ms	9964 KB	Ok
17	Correct	9 ms	9964 KB	Ok
18	Correct	12 ms	10092 KB	Ok
19	Correct	24 ms	10604 KB	Ok
20	Correct	15 ms	10604 KB	Ok
21	Correct	28 ms	10764 KB	Ok
22	Correct	18 ms	10764 KB	Ok
23	Correct	8 ms	10764 KB	Ok
24	Correct	8 ms	10764 KB	Ok
25	Correct	8 ms	10764 KB	Ok
26	Correct	9 ms	10764 KB	Ok
27	Correct	11 ms	10764 KB	Ok
28	Correct	9 ms	10764 KB	Ok
29	Correct	9 ms	10764 KB	Ok
30	Correct	8 ms	10764 KB	Ok
31	Correct	8 ms	10764 KB	Ok
32	Correct	11 ms	10764 KB	Ok
33	Correct	9 ms	10764 KB	Ok
34	Correct	10 ms	10764 KB	Ok
35	Correct	8 ms	10764 KB	Ok
36	Correct	8 ms	10764 KB	Ok
37	Correct	9 ms	10764 KB	Ok
38	Correct	8 ms	10764 KB	Ok
39	Correct	336 ms	19284 KB	Ok
40	Correct	324 ms	20048 KB	Ok
41	Correct	610 ms	21996 KB	Ok
42	Correct	436 ms	21996 KB	Ok
43	Correct	267 ms	21996 KB	Ok
44	Correct	453 ms	21996 KB	Ok
45	Correct	13 ms	21996 KB	Ok
46	Correct	15 ms	21996 KB	Ok
47	Correct	14 ms	21996 KB	Ok
48	Correct	13 ms	21996 KB	Ok
49	Correct	12 ms	21996 KB	Ok
50	Correct	12 ms	21996 KB	Ok
51	Correct	17 ms	21996 KB	Ok
52	Correct	19 ms	21996 KB	Ok
53	Correct	19 ms	21996 KB	Ok
54	Correct	13 ms	21996 KB	Ok
55	Correct	25 ms	21996 KB	Ok
56	Correct	21 ms	21996 KB	Ok
57	Correct	28 ms	21996 KB	Ok
58	Correct	19 ms	21996 KB	Ok
59	Correct	21 ms	21996 KB	Ok
60	Correct	20 ms	21996 KB	Ok
61	Correct	21 ms	21996 KB	Ok
62	Correct	19 ms	21996 KB	Ok
63	Correct	19 ms	21996 KB	Ok
64	Correct	22 ms	21996 KB	Ok
65	Correct	248 ms	21996 KB	Ok
66	Correct	288 ms	21996 KB	Ok
67	Correct	299 ms	21996 KB	Ok
68	Correct	214 ms	21996 KB	Ok
69	Correct	272 ms	21996 KB	Ok
70	Correct	262 ms	21996 KB	Ok
71	Correct	212 ms	21996 KB	Ok
72	Correct	210 ms	21996 KB	Ok
73	Correct	308 ms	21996 KB	Ok
74	Correct	219 ms	21996 KB	Ok
75	Correct	289 ms	21996 KB	Ok
76	Correct	273 ms	21996 KB	Ok
77	Correct	243 ms	21996 KB	Ok
78	Correct	244 ms	21996 KB	Ok
79	Correct	268 ms	21996 KB	Ok
80	Correct	562 ms	21996 KB	Ok
81	Correct	591 ms	21996 KB	Ok
82	Correct	549 ms	21996 KB	Ok
83	Correct	588 ms	21996 KB	Ok
84	Correct	522 ms	21996 KB	Ok
85	Correct	499 ms	21996 KB	Ok
86	Correct	534 ms	21996 KB	Ok
87	Correct	613 ms	21996 KB	Ok
88	Correct	517 ms	21996 KB	Ok
89	Correct	547 ms	21996 KB	Ok
90	Correct	572 ms	21996 KB	Ok
91	Correct	520 ms	21996 KB	Ok
92	Correct	530 ms	21996 KB	Ok
93	Correct	522 ms	21996 KB	Ok
94	Correct	516 ms	21996 KB	Ok
95	Correct	676 ms	23148 KB	Ok
96	Correct	1052 ms	29436 KB	Ok
97	Correct	1010 ms	29436 KB	Ok
98	Correct	746 ms	29436 KB	Ok
99	Correct	903 ms	29436 KB	Ok
100	Correct	954 ms	29436 KB	Ok
101	Correct	1014 ms	29436 KB	Ok
102	Correct	922 ms	29436 KB	Ok
103	Correct	952 ms	29436 KB	Ok
104	Correct	1079 ms	29436 KB	Ok
105	Correct	1044 ms	29436 KB	Ok
106	Correct	860 ms	29436 KB	Ok
107	Correct	952 ms	29436 KB	Ok
108	Correct	1110 ms	29436 KB	Ok
109	Correct	970 ms	29436 KB	Ok
110	Execution timed out	2059 ms	33324 KB	Time limit exceeded
111	Halted	0 ms	0 KB	-

답안 #40455

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