oj.uz

Submission #745073

# Submission time Handle Problem Language Result Execution time Memory
745073 2023-05-19T11:24:47 Z 박상훈(#9964) Event Hopping (BOI22_events) C++17
10 / 100
 1500 ms 1048 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 1e9 + 100;
int n, S[100100], E[100100];

bool ok(int x, int y){
	return E[x] <= E[y];
}

void naive(int x, int y){
	if (!ok(x, y)){
		printf("impossible\n");
		return;
	}

	if (x==y){
		printf("0\n");
		return;
	}

	int l = S[y], r = E[y], ans = 1;
	while(true){
		if (l<=E[x]){
			printf("%d\n", ans);
			return;
		}

		int nl = INF;
		for (int i=1;i<=n;i++) if (l<=E[i] && E[i]<=r){
			nl = min(nl, S[i]);
		}
		if (l==nl) break;
		l = nl;
		ans++;
	}

	printf("impossible\n");
}

void solve(int x, int y){
	if (!ok(x, y)){
		printf("impossible\n");
		return;
	}

	if (x==y){
		printf("0\n");
		return;
	}
}

int main(){
	int q;
	scanf("%d %d", &n, &q);
	for (int i=1;i<=n;i++) scanf("%d %d", S+i, E+i);

	while(q--){
		int x, y;
		scanf("%d %d", &x, &y);
		naive(x, y);
	}
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:56:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   56 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:57:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  for (int i=1;i<=n;i++) scanf("%d %d", S+i, E+i);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~
events.cpp:61:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |   scanf("%d %d", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1580 ms 988 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 186 ms 212 KB Output is correct
4 Correct 23 ms 212 KB Output is correct
5 Correct 39 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 186 ms 212 KB Output is correct
4 Correct 23 ms 212 KB Output is correct
5 Correct 39 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 183 ms 304 KB Output is correct
13 Correct 22 ms 212 KB Output is correct
14 Correct 39 ms 300 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Execution timed out 1587 ms 340 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 186 ms 212 KB Output is correct
4 Correct 23 ms 212 KB Output is correct
5 Correct 39 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 185 ms 304 KB Output is correct
13 Correct 23 ms 324 KB Output is correct
14 Correct 37 ms 312 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Execution timed out 1585 ms 1044 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1563 ms 1048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Execution timed out 1580 ms 988 KB Time limit exceeded
3 Halted 0 ms 0 KB -