oj.uz

Submission #210853

# Submission time Handle Problem Language Result Execution time Memory
210853 2020-03-18T21:38:13 Z Lawliet Building Skyscrapers (CEOI19_skyscrapers) C++17
54 / 100
 757 ms 51560 KB 
#include <bits/stdc++.h>
 
using namespace std;
typedef pair<int,int> pii;
 
const int MAXN = 150010;
 
int dx[] = { 0 , 0 , 1 , -1 , 1 , -1 , 1 , -1 };
int dy[] = { 1 , -1 , 0 , 0 , 1 , 1 , -1 , -1 };
 
int n, t;
 
pii v[MAXN];
 
vector< int > ans;
 
map< pii , int > ind;
map< pii , bool > marc;
 
void topologicalSorting(int iniX, int iniY)
{
	set< pii > s;
 
	s.insert( { iniX , iniY } );
	marc[ { iniX , iniY } ] = true;
 
	while( !s.empty() )
	{
		int curX = s.begin()->first;
		int curY = s.begin()->second;
		s.erase( s.begin() );
 
		ans.push_back( ind[ { curX , curY } ] );
 
		for(int d = 0 ; d < 8 ; d++)
		{
			int nextX = curX + dx[d];
			int nextY = curY + dy[d];
 
			if( ind[ { nextX , nextY } ] == 0 ) continue;
			if( marc[ { nextX , nextY } ] ) continue;
 
			s.insert( { nextX , nextY } );
			marc[ { nextX , nextY } ] = true;
		}
	}
}
 
int main()
{
	scanf("%d %d",&n,&t);
 
	for(int i = 1 ; i <= n ; i++)
	{
		int x, y;
		scanf("%d %d",&x,&y);
 
		v[i] = { x , y };
		ind[ v[i] ] = i;
	}
 
	int ini = 1;
 
	for(int i = 2 ; i <= n ; i++)
		if( v[i].first < v[ini].first ) ini = i;
 
	topologicalSorting( v[ini].first , v[ini].second );
 
	if( ans.size() != n )
	{
		printf("NO\n");
		return 0;
	}
 
	printf("YES\n");
 
	for(int i = 0 ; i < ans.size() ; i++)
		printf("%d\n",ans[i]);
}

Compilation message

skyscrapers.cpp: In function 'int main()':
skyscrapers.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if( ans.size() != n )
      ~~~~~~~~~~~^~~~
skyscrapers.cpp:77:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < ans.size() ; i++)
                  ~~^~~~~~~~~~~~
skyscrapers.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&t);
  ~~~~~^~~~~~~~~~~~~~~
skyscrapers.cpp:56:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&x,&y);
   ~~~~~^~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB ans=YES N=1
2 Correct 7 ms 256 KB ans=YES N=4
3 Correct 7 ms 256 KB ans=NO N=4
4 Correct 7 ms 348 KB ans=YES N=5
5 Correct 7 ms 376 KB ans=YES N=9
6 Correct 7 ms 404 KB ans=YES N=5
7 Correct 7 ms 372 KB ans=NO N=9
8 Correct 7 ms 256 KB ans=NO N=10
9 Correct 7 ms 448 KB ans=YES N=10
10 Correct 7 ms 372 KB ans=YES N=10
11 Correct 8 ms 312 KB ans=YES N=10
12 Correct 6 ms 256 KB ans=YES N=9
13 Correct 7 ms 256 KB ans=YES N=9
14 Correct 7 ms 364 KB ans=YES N=8
15 Correct 7 ms 364 KB ans=YES N=8
16 Correct 8 ms 376 KB ans=NO N=2

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB ans=YES N=1
2 Correct 7 ms 256 KB ans=YES N=4
3 Correct 7 ms 256 KB ans=NO N=4
4 Correct 7 ms 348 KB ans=YES N=5
5 Correct 7 ms 376 KB ans=YES N=9
6 Correct 7 ms 404 KB ans=YES N=5
7 Correct 7 ms 372 KB ans=NO N=9
8 Correct 7 ms 256 KB ans=NO N=10
9 Correct 7 ms 448 KB ans=YES N=10
10 Correct 7 ms 372 KB ans=YES N=10
11 Correct 8 ms 312 KB ans=YES N=10
12 Correct 6 ms 256 KB ans=YES N=9
13 Correct 7 ms 256 KB ans=YES N=9
14 Correct 7 ms 364 KB ans=YES N=8
15 Correct 7 ms 364 KB ans=YES N=8
16 Correct 8 ms 376 KB ans=NO N=2
17 Correct 8 ms 380 KB ans=YES N=17
18 Correct 7 ms 376 KB ans=YES N=25
19 Correct 9 ms 296 KB ans=YES N=100
20 Correct 8 ms 376 KB ans=YES N=185
21 Correct 8 ms 376 KB ans=NO N=174
22 Correct 7 ms 376 KB ans=YES N=90
23 Correct 9 ms 380 KB ans=YES N=63
24 Correct 7 ms 376 KB ans=YES N=87
25 Correct 7 ms 376 KB ans=YES N=183
26 Correct 7 ms 376 KB ans=YES N=188
27 Correct 8 ms 404 KB ans=YES N=183
28 Correct 9 ms 404 KB ans=YES N=189
29 Correct 8 ms 376 KB ans=YES N=200
30 Correct 7 ms 376 KB ans=YES N=190
31 Correct 7 ms 420 KB ans=YES N=187
32 Correct 7 ms 296 KB ans=YES N=187
33 Correct 9 ms 376 KB ans=YES N=182
34 Correct 9 ms 376 KB ans=YES N=184
35 Correct 7 ms 376 KB ans=YES N=188
36 Correct 7 ms 376 KB ans=YES N=181
37 Correct 9 ms 376 KB ans=YES N=188
38 Correct 7 ms 376 KB ans=YES N=191
39 Correct 8 ms 376 KB ans=YES N=196
40 Correct 7 ms 376 KB ans=YES N=196
41 Correct 6 ms 376 KB ans=YES N=196
42 Correct 8 ms 376 KB ans=YES N=196
43 Correct 7 ms 376 KB ans=YES N=195

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB ans=YES N=1
2 Correct 7 ms 256 KB ans=YES N=4
3 Correct 7 ms 256 KB ans=NO N=4
4 Correct 7 ms 348 KB ans=YES N=5
5 Correct 7 ms 376 KB ans=YES N=9
6 Correct 7 ms 404 KB ans=YES N=5
7 Correct 7 ms 372 KB ans=NO N=9
8 Correct 7 ms 256 KB ans=NO N=10
9 Correct 7 ms 448 KB ans=YES N=10
10 Correct 7 ms 372 KB ans=YES N=10
11 Correct 8 ms 312 KB ans=YES N=10
12 Correct 6 ms 256 KB ans=YES N=9
13 Correct 7 ms 256 KB ans=YES N=9
14 Correct 7 ms 364 KB ans=YES N=8
15 Correct 7 ms 364 KB ans=YES N=8
16 Correct 8 ms 376 KB ans=NO N=2
17 Correct 8 ms 380 KB ans=YES N=17
18 Correct 7 ms 376 KB ans=YES N=25
19 Correct 9 ms 296 KB ans=YES N=100
20 Correct 8 ms 376 KB ans=YES N=185
21 Correct 8 ms 376 KB ans=NO N=174
22 Correct 7 ms 376 KB ans=YES N=90
23 Correct 9 ms 380 KB ans=YES N=63
24 Correct 7 ms 376 KB ans=YES N=87
25 Correct 7 ms 376 KB ans=YES N=183
26 Correct 7 ms 376 KB ans=YES N=188
27 Correct 8 ms 404 KB ans=YES N=183
28 Correct 9 ms 404 KB ans=YES N=189
29 Correct 8 ms 376 KB ans=YES N=200
30 Correct 7 ms 376 KB ans=YES N=190
31 Correct 7 ms 420 KB ans=YES N=187
32 Correct 7 ms 296 KB ans=YES N=187
33 Correct 9 ms 376 KB ans=YES N=182
34 Correct 9 ms 376 KB ans=YES N=184
35 Correct 7 ms 376 KB ans=YES N=188
36 Correct 7 ms 376 KB ans=YES N=181
37 Correct 9 ms 376 KB ans=YES N=188
38 Correct 7 ms 376 KB ans=YES N=191
39 Correct 8 ms 376 KB ans=YES N=196
40 Correct 7 ms 376 KB ans=YES N=196
41 Correct 6 ms 376 KB ans=YES N=196
42 Correct 8 ms 376 KB ans=YES N=196
43 Correct 7 ms 376 KB ans=YES N=195
44 Correct 10 ms 532 KB ans=NO N=1934
45 Correct 9 ms 532 KB ans=NO N=1965
46 Correct 14 ms 660 KB ans=YES N=1824
47 Correct 14 ms 636 KB ans=YES N=1981
48 Correct 14 ms 680 KB ans=YES N=1814
49 Correct 12 ms 760 KB ans=YES N=1854
50 Correct 12 ms 636 KB ans=YES N=1831
51 Correct 13 ms 760 KB ans=YES N=2000
52 Correct 13 ms 788 KB ans=YES N=1847
53 Correct 13 ms 888 KB ans=YES N=1819
54 Correct 13 ms 760 KB ans=YES N=1986
55 Correct 13 ms 888 KB ans=YES N=2000
56 Correct 15 ms 888 KB ans=YES N=1834
57 Correct 12 ms 888 KB ans=YES N=1860
58 Correct 13 ms 892 KB ans=YES N=1898
59 Correct 14 ms 760 KB ans=YES N=1832
60 Correct 13 ms 1016 KB ans=YES N=1929
61 Correct 13 ms 760 KB ans=YES N=1919
62 Correct 13 ms 888 KB ans=YES N=1882
63 Correct 14 ms 1012 KB ans=YES N=1922
64 Correct 12 ms 680 KB ans=YES N=1989
65 Correct 12 ms 920 KB ans=YES N=1978
66 Correct 14 ms 888 KB ans=YES N=1867
67 Correct 11 ms 888 KB ans=YES N=1942

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 532 KB ans=NO N=1934
2 Correct 9 ms 508 KB ans=NO N=1965
3 Incorrect 13 ms 660 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB ans=YES N=1
2 Correct 7 ms 256 KB ans=YES N=4
3 Correct 7 ms 256 KB ans=NO N=4
4 Correct 7 ms 348 KB ans=YES N=5
5 Correct 7 ms 376 KB ans=YES N=9
6 Correct 7 ms 404 KB ans=YES N=5
7 Correct 7 ms 372 KB ans=NO N=9
8 Correct 7 ms 256 KB ans=NO N=10
9 Correct 7 ms 448 KB ans=YES N=10
10 Correct 7 ms 372 KB ans=YES N=10
11 Correct 8 ms 312 KB ans=YES N=10
12 Correct 6 ms 256 KB ans=YES N=9
13 Correct 7 ms 256 KB ans=YES N=9
14 Correct 7 ms 364 KB ans=YES N=8
15 Correct 7 ms 364 KB ans=YES N=8
16 Correct 8 ms 376 KB ans=NO N=2
17 Correct 8 ms 380 KB ans=YES N=17
18 Correct 7 ms 376 KB ans=YES N=25
19 Correct 9 ms 296 KB ans=YES N=100
20 Correct 8 ms 376 KB ans=YES N=185
21 Correct 8 ms 376 KB ans=NO N=174
22 Correct 7 ms 376 KB ans=YES N=90
23 Correct 9 ms 380 KB ans=YES N=63
24 Correct 7 ms 376 KB ans=YES N=87
25 Correct 7 ms 376 KB ans=YES N=183
26 Correct 7 ms 376 KB ans=YES N=188
27 Correct 8 ms 404 KB ans=YES N=183
28 Correct 9 ms 404 KB ans=YES N=189
29 Correct 8 ms 376 KB ans=YES N=200
30 Correct 7 ms 376 KB ans=YES N=190
31 Correct 7 ms 420 KB ans=YES N=187
32 Correct 7 ms 296 KB ans=YES N=187
33 Correct 9 ms 376 KB ans=YES N=182
34 Correct 9 ms 376 KB ans=YES N=184
35 Correct 7 ms 376 KB ans=YES N=188
36 Correct 7 ms 376 KB ans=YES N=181
37 Correct 9 ms 376 KB ans=YES N=188
38 Correct 7 ms 376 KB ans=YES N=191
39 Correct 8 ms 376 KB ans=YES N=196
40 Correct 7 ms 376 KB ans=YES N=196
41 Correct 6 ms 376 KB ans=YES N=196
42 Correct 8 ms 376 KB ans=YES N=196
43 Correct 7 ms 376 KB ans=YES N=195
44 Correct 10 ms 532 KB ans=NO N=1934
45 Correct 9 ms 532 KB ans=NO N=1965
46 Correct 14 ms 660 KB ans=YES N=1824
47 Correct 14 ms 636 KB ans=YES N=1981
48 Correct 14 ms 680 KB ans=YES N=1814
49 Correct 12 ms 760 KB ans=YES N=1854
50 Correct 12 ms 636 KB ans=YES N=1831
51 Correct 13 ms 760 KB ans=YES N=2000
52 Correct 13 ms 788 KB ans=YES N=1847
53 Correct 13 ms 888 KB ans=YES N=1819
54 Correct 13 ms 760 KB ans=YES N=1986
55 Correct 13 ms 888 KB ans=YES N=2000
56 Correct 15 ms 888 KB ans=YES N=1834
57 Correct 12 ms 888 KB ans=YES N=1860
58 Correct 13 ms 892 KB ans=YES N=1898
59 Correct 14 ms 760 KB ans=YES N=1832
60 Correct 13 ms 1016 KB ans=YES N=1929
61 Correct 13 ms 760 KB ans=YES N=1919
62 Correct 13 ms 888 KB ans=YES N=1882
63 Correct 14 ms 1012 KB ans=YES N=1922
64 Correct 12 ms 680 KB ans=YES N=1989
65 Correct 12 ms 920 KB ans=YES N=1978
66 Correct 14 ms 888 KB ans=YES N=1867
67 Correct 11 ms 888 KB ans=YES N=1942
68 Correct 281 ms 12560 KB ans=NO N=66151
69 Correct 92 ms 5368 KB ans=NO N=64333
70 Correct 288 ms 10960 KB ans=YES N=69316
71 Correct 259 ms 10544 KB ans=YES N=66695
72 Correct 298 ms 10952 KB ans=YES N=68436
73 Correct 313 ms 11248 KB ans=YES N=70000
74 Correct 270 ms 11056 KB ans=YES N=68501
75 Correct 316 ms 11604 KB ans=YES N=70000
76 Correct 231 ms 11636 KB ans=YES N=65009
77 Correct 247 ms 15988 KB ans=YES N=67007
78 Correct 247 ms 18060 KB ans=YES N=66357
79 Correct 246 ms 19428 KB ans=YES N=65430
80 Correct 264 ms 18796 KB ans=YES N=65790
81 Correct 266 ms 17880 KB ans=YES N=66020
82 Correct 248 ms 16880 KB ans=YES N=65809
83 Correct 239 ms 12908 KB ans=YES N=65651
84 Correct 291 ms 23556 KB ans=YES N=68040
85 Correct 269 ms 20932 KB ans=YES N=66570
86 Correct 225 ms 11128 KB ans=YES N=65421
87 Correct 274 ms 12140 KB ans=YES N=68351
88 Correct 231 ms 10716 KB ans=YES N=67027
89 Correct 216 ms 15280 KB ans=YES N=68879
90 Correct 234 ms 12272 KB ans=YES N=67256
91 Correct 612 ms 23864 KB ans=YES N=148315
92 Correct 189 ms 11756 KB ans=NO N=142745
93 Correct 226 ms 14016 KB ans=NO N=148443
94 Correct 609 ms 24984 KB ans=YES N=148328
95 Correct 602 ms 24944 KB ans=YES N=147855
96 Correct 641 ms 25548 KB ans=YES N=150000
97 Correct 604 ms 24492 KB ans=YES N=144725
98 Correct 616 ms 25200 KB ans=YES N=149445
99 Correct 602 ms 24920 KB ans=YES N=144455
100 Correct 586 ms 24384 KB ans=YES N=143487
101 Correct 682 ms 25124 KB ans=YES N=149688
102 Correct 641 ms 36296 KB ans=YES N=141481
103 Correct 757 ms 48116 KB ans=YES N=147430
104 Correct 643 ms 31076 KB ans=YES N=142247
105 Correct 685 ms 35804 KB ans=YES N=149941
106 Correct 678 ms 45540 KB ans=YES N=141635
107 Correct 707 ms 42224 KB ans=YES N=142896
108 Correct 639 ms 45716 KB ans=YES N=142069
109 Correct 609 ms 26144 KB ans=YES N=142378
110 Correct 636 ms 39628 KB ans=YES N=150000
111 Correct 611 ms 51560 KB ans=YES N=141452
112 Correct 607 ms 49168 KB ans=YES N=134453
113 Correct 572 ms 51524 KB ans=YES N=144172

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 12660 KB ans=NO N=66151
2 Correct 73 ms 5368 KB ans=NO N=64333
3 Incorrect 251 ms 10996 KB Contestant's solution is not lexicographically largest at index 69316 (69235 vs 7320)
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 532 KB ans=NO N=1934
2 Correct 9 ms 508 KB ans=NO N=1965
3 Incorrect 13 ms 660 KB Contestant's solution is not lexicographically largest at index 1824 (1813 vs 1702)
4 Halted 0 ms 0 KB -