oj.uz

Submission #40453

# Submission time Handle Problem Language Result Execution time Memory
40453 2018-02-01T16:37:04 Z Pajaraja Nice sequence (IZhO18_sequence) C++14
76 / 100
 614 ms 17264 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,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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -