oj.uz

Submission #40452

# Submission time Handle Problem Language Result Execution time Memory
40452 2018-02-01T16:35:45 Z Pajaraja Nice sequence (IZhO18_sequence) C++14
76 / 100
 669 ms 27000 KB 
#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,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

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Ok
2 Correct 6 ms 5088 KB Ok
3 Correct 5 ms 5288 KB Ok
4 Correct 5 ms 5288 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 5 ms 5340 KB Ok
7 Correct 5 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 5 ms 5340 KB Ok
10 Correct 5 ms 5340 KB Ok
11 Correct 5 ms 5340 KB Ok
12 Correct 5 ms 5340 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5340 KB Ok
2 Correct 5 ms 5340 KB Ok
3 Correct 5 ms 5340 KB Ok
4 Correct 7 ms 5340 KB Ok
5 Correct 5 ms 5340 KB Ok
6 Correct 10 ms 5356 KB Ok
7 Correct 38 ms 5996 KB Ok
8 Correct 19 ms 5996 KB Ok
9 Correct 47 ms 6140 KB Ok
10 Correct 23 ms 6140 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6140 KB Ok
2 Correct 5 ms 6140 KB Ok
3 Correct 5 ms 6140 KB Ok
4 Correct 5 ms 6140 KB Ok
5 Correct 5 ms 6140 KB Ok
6 Correct 7 ms 6140 KB Ok
7 Correct 5 ms 6140 KB Ok
8 Correct 5 ms 6140 KB Ok
9 Correct 5 ms 6140 KB Ok
10 Correct 5 ms 6140 KB Ok
11 Correct 6 ms 6140 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6140 KB Ok
2 Correct 5 ms 6140 KB Ok
3 Correct 5 ms 6140 KB Ok
4 Correct 5 ms 6140 KB Ok
5 Correct 5 ms 6140 KB Ok
6 Correct 356 ms 14724 KB Ok
7 Correct 364 ms 15216 KB Ok
8 Correct 610 ms 17320 KB Ok
9 Correct 459 ms 17320 KB Ok
10 Correct 258 ms 17320 KB Ok
11 Correct 430 ms 17320 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Ok
2 Correct 6 ms 5088 KB Ok
3 Correct 5 ms 5288 KB Ok
4 Correct 5 ms 5288 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 5 ms 5340 KB Ok
7 Correct 5 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 5 ms 5340 KB Ok
10 Correct 5 ms 5340 KB Ok
11 Correct 5 ms 5340 KB Ok
12 Correct 5 ms 5340 KB Ok
13 Correct 6 ms 6140 KB Ok
14 Correct 5 ms 6140 KB Ok
15 Correct 5 ms 6140 KB Ok
16 Correct 5 ms 6140 KB Ok
17 Correct 5 ms 6140 KB Ok
18 Correct 7 ms 6140 KB Ok
19 Correct 5 ms 6140 KB Ok
20 Correct 5 ms 6140 KB Ok
21 Correct 5 ms 6140 KB Ok
22 Correct 5 ms 6140 KB Ok
23 Correct 6 ms 6140 KB Ok
24 Correct 10 ms 17320 KB Ok
25 Correct 10 ms 17320 KB Ok
26 Correct 11 ms 17320 KB Ok
27 Correct 10 ms 17320 KB Ok
28 Correct 8 ms 17320 KB Ok
29 Correct 8 ms 17320 KB Ok
30 Correct 8 ms 17320 KB Ok
31 Correct 12 ms 17320 KB Ok
32 Correct 13 ms 17320 KB Ok
33 Correct 9 ms 17320 KB Ok
34 Correct 15 ms 17320 KB Ok
35 Correct 15 ms 17320 KB Ok
36 Correct 15 ms 17320 KB Ok
37 Correct 16 ms 17320 KB Ok
38 Correct 18 ms 17320 KB Ok
39 Correct 15 ms 17320 KB Ok
40 Correct 16 ms 17320 KB Ok
41 Correct 15 ms 17320 KB Ok
42 Correct 16 ms 17320 KB Ok
43 Correct 16 ms 17320 KB Ok

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Ok
2 Correct 6 ms 5088 KB Ok
3 Correct 5 ms 5288 KB Ok
4 Correct 5 ms 5288 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 5 ms 5340 KB Ok
7 Correct 5 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 5 ms 5340 KB Ok
10 Correct 5 ms 5340 KB Ok
11 Correct 5 ms 5340 KB Ok
12 Correct 5 ms 5340 KB Ok
13 Correct 5 ms 5340 KB Ok
14 Correct 5 ms 5340 KB Ok
15 Correct 5 ms 5340 KB Ok
16 Correct 7 ms 5340 KB Ok
17 Correct 5 ms 5340 KB Ok
18 Correct 10 ms 5356 KB Ok
19 Correct 38 ms 5996 KB Ok
20 Correct 19 ms 5996 KB Ok
21 Correct 47 ms 6140 KB Ok
22 Correct 23 ms 6140 KB Ok
23 Correct 6 ms 6140 KB Ok
24 Correct 5 ms 6140 KB Ok
25 Correct 5 ms 6140 KB Ok
26 Correct 5 ms 6140 KB Ok
27 Correct 5 ms 6140 KB Ok
28 Correct 7 ms 6140 KB Ok
29 Correct 5 ms 6140 KB Ok
30 Correct 5 ms 6140 KB Ok
31 Correct 5 ms 6140 KB Ok
32 Correct 5 ms 6140 KB Ok
33 Correct 6 ms 6140 KB Ok
34 Correct 10 ms 17320 KB Ok
35 Correct 10 ms 17320 KB Ok
36 Correct 11 ms 17320 KB Ok
37 Correct 10 ms 17320 KB Ok
38 Correct 8 ms 17320 KB Ok
39 Correct 8 ms 17320 KB Ok
40 Correct 8 ms 17320 KB Ok
41 Correct 12 ms 17320 KB Ok
42 Correct 13 ms 17320 KB Ok
43 Correct 9 ms 17320 KB Ok
44 Correct 15 ms 17320 KB Ok
45 Correct 15 ms 17320 KB Ok
46 Correct 15 ms 17320 KB Ok
47 Correct 16 ms 17320 KB Ok
48 Correct 18 ms 17320 KB Ok
49 Correct 15 ms 17320 KB Ok
50 Correct 16 ms 17320 KB Ok
51 Correct 15 ms 17320 KB Ok
52 Correct 16 ms 17320 KB Ok
53 Correct 16 ms 17320 KB Ok
54 Correct 240 ms 17320 KB Ok
55 Correct 288 ms 17320 KB Ok
56 Correct 300 ms 17320 KB Ok
57 Correct 211 ms 17320 KB Ok
58 Correct 272 ms 17320 KB Ok
59 Correct 244 ms 17320 KB Ok
60 Correct 218 ms 17320 KB Ok
61 Correct 243 ms 17320 KB Ok
62 Correct 306 ms 17320 KB Ok
63 Correct 220 ms 17320 KB Ok
64 Correct 303 ms 17320 KB Ok
65 Correct 290 ms 17320 KB Ok
66 Correct 253 ms 17320 KB Ok
67 Correct 206 ms 17320 KB Ok
68 Correct 254 ms 17320 KB Ok
69 Correct 587 ms 17320 KB Ok
70 Correct 669 ms 17320 KB Ok
71 Correct 584 ms 17320 KB Ok
72 Correct 623 ms 17320 KB Ok
73 Correct 555 ms 17320 KB Ok
74 Correct 535 ms 17320 KB Ok
75 Correct 557 ms 17320 KB Ok
76 Correct 600 ms 17320 KB Ok
77 Correct 511 ms 17320 KB Ok
78 Correct 591 ms 17320 KB Ok
79 Correct 604 ms 17320 KB Ok
80 Correct 535 ms 17320 KB Ok
81 Correct 565 ms 17320 KB Ok
82 Correct 539 ms 17320 KB Ok
83 Correct 534 ms 17320 KB Ok

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4984 KB Ok
2 Correct 6 ms 5088 KB Ok
3 Correct 5 ms 5288 KB Ok
4 Correct 5 ms 5288 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 5 ms 5340 KB Ok
7 Correct 5 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 5 ms 5340 KB Ok
10 Correct 5 ms 5340 KB Ok
11 Correct 5 ms 5340 KB Ok
12 Correct 5 ms 5340 KB Ok
13 Correct 5 ms 5340 KB Ok
14 Correct 5 ms 5340 KB Ok
15 Correct 5 ms 5340 KB Ok
16 Correct 7 ms 5340 KB Ok
17 Correct 5 ms 5340 KB Ok
18 Correct 10 ms 5356 KB Ok
19 Correct 38 ms 5996 KB Ok
20 Correct 19 ms 5996 KB Ok
21 Correct 47 ms 6140 KB Ok
22 Correct 23 ms 6140 KB Ok
23 Correct 6 ms 6140 KB Ok
24 Correct 5 ms 6140 KB Ok
25 Correct 5 ms 6140 KB Ok
26 Correct 5 ms 6140 KB Ok
27 Correct 5 ms 6140 KB Ok
28 Correct 7 ms 6140 KB Ok
29 Correct 5 ms 6140 KB Ok
30 Correct 5 ms 6140 KB Ok
31 Correct 5 ms 6140 KB Ok
32 Correct 5 ms 6140 KB Ok
33 Correct 6 ms 6140 KB Ok
34 Correct 5 ms 6140 KB Ok
35 Correct 5 ms 6140 KB Ok
36 Correct 5 ms 6140 KB Ok
37 Correct 5 ms 6140 KB Ok
38 Correct 5 ms 6140 KB Ok
39 Correct 356 ms 14724 KB Ok
40 Correct 364 ms 15216 KB Ok
41 Correct 610 ms 17320 KB Ok
42 Correct 459 ms 17320 KB Ok
43 Correct 258 ms 17320 KB Ok
44 Correct 430 ms 17320 KB Ok
45 Correct 10 ms 17320 KB Ok
46 Correct 10 ms 17320 KB Ok
47 Correct 11 ms 17320 KB Ok
48 Correct 10 ms 17320 KB Ok
49 Correct 8 ms 17320 KB Ok
50 Correct 8 ms 17320 KB Ok
51 Correct 8 ms 17320 KB Ok
52 Correct 12 ms 17320 KB Ok
53 Correct 13 ms 17320 KB Ok
54 Correct 9 ms 17320 KB Ok
55 Correct 15 ms 17320 KB Ok
56 Correct 15 ms 17320 KB Ok
57 Correct 15 ms 17320 KB Ok
58 Correct 16 ms 17320 KB Ok
59 Correct 18 ms 17320 KB Ok
60 Correct 15 ms 17320 KB Ok
61 Correct 16 ms 17320 KB Ok
62 Correct 15 ms 17320 KB Ok
63 Correct 16 ms 17320 KB Ok
64 Correct 16 ms 17320 KB Ok
65 Correct 240 ms 17320 KB Ok
66 Correct 288 ms 17320 KB Ok
67 Correct 300 ms 17320 KB Ok
68 Correct 211 ms 17320 KB Ok
69 Correct 272 ms 17320 KB Ok
70 Correct 244 ms 17320 KB Ok
71 Correct 218 ms 17320 KB Ok
72 Correct 243 ms 17320 KB Ok
73 Correct 306 ms 17320 KB Ok
74 Correct 220 ms 17320 KB Ok
75 Correct 303 ms 17320 KB Ok
76 Correct 290 ms 17320 KB Ok
77 Correct 253 ms 17320 KB Ok
78 Correct 206 ms 17320 KB Ok
79 Correct 254 ms 17320 KB Ok
80 Correct 587 ms 17320 KB Ok
81 Correct 669 ms 17320 KB Ok
82 Correct 584 ms 17320 KB Ok
83 Correct 623 ms 17320 KB Ok
84 Correct 555 ms 17320 KB Ok
85 Correct 535 ms 17320 KB Ok
86 Correct 557 ms 17320 KB Ok
87 Correct 600 ms 17320 KB Ok
88 Correct 511 ms 17320 KB Ok
89 Correct 591 ms 17320 KB Ok
90 Correct 604 ms 17320 KB Ok
91 Correct 535 ms 17320 KB Ok
92 Correct 565 ms 17320 KB Ok
93 Correct 539 ms 17320 KB Ok
94 Correct 534 ms 17320 KB Ok
95 Runtime error 263 ms 27000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
96 Halted 0 ms 0 KB -