oj.uz

Submission #595792

# Submission time Handle Problem Language Result Execution time Memory
595792 2022-07-14T06:50:15 Z dooompy MP3 Player (CEOI10_mp3player) C++17
100 / 100
 38 ms 5492 KB 
// solution written by Peter Fulla
#include <cstdio>
#include <algorithm>
#include <vector>
#define REP(i, n) for(int i = 0; i < (int)(n); ++i)
#define FORD(i, a, b) for(int i = (int)(a); i >= (int)(b); --i)
using namespace std;

struct Function{
	int a, b, c;
};

int N, V, R, N2;
vector<char> Z;
vector<int> T, P;
vector<Function> F;

bool cmp(const int a, const int b){
	return T[a] < T[b];
}

int main(){
	scanf("%d %d %d ", &N, &V, &R);
	Z.resize(N);
	T.resize(N);
	REP(i, N)
		scanf("%c %d ", &Z[i], &T[i]);

	FORD(i, N - 1, 1)
		T[i] -= T[i - 1];

	P.resize(N - 1);
	REP(i, N - 1)
		P[i] = i + 1;

	sort(P.begin(), P.end(), cmp);

	N2 = 1;
	while(N2 < N)
		N2 *= 2;

	F.resize(2 * N2, (Function){0, V, 0});


	int resT = 0, resS = R;

	REP(i, N - 1){
		int j = N2 + P[i];

		if(Z[P[i]] == '+')
			F[j] = (Function){0, V - 1, 1};
		else
			F[j] = (Function){1, V, -1};

		while(j > 1){
			j /= 2;

			F[j].a = max(F[2 * j].a, F[2 * j + 1].a - F[2 * j].c);
			F[j].b = min(F[2 * j].b, F[2 * j + 1].b - F[2 * j].c);

			if(F[j].a <= F[j].b)
				F[j].c = F[2 * j].c + F[2 * j + 1].c;
			else if(F[2 * j].a > F[2 * j + 1].b - F[2 * j].c)
				F[j] = (Function){F[2 * j + 1].b, F[2 * j + 1].b, F[2 * j + 1].c};
			else
				F[j] = (Function){F[2 * j + 1].a, F[2 * j + 1].a, F[2 * j + 1].c};
		}

		if(i == N - 2 || T[P[i]] != T[P[i + 1]]){
			if(F[1].a + F[1].c <= R && R < F[1].b + F[1].c){
				resT = i;
				resS = R - F[1].c;
			}else if(R == F[1].b + F[1].c){
				resT = i;
				resS = V;
			}
		}
	}

	if(resT == N - 2)
		printf("infinity\n");
	else
		printf("%d %d\n", T[P[resT + 1]] - 1, resS);
}

Compilation message

mp3player.cpp: In function 'int main()':
mp3player.cpp:23:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  scanf("%d %d %d ", &N, &V, &R);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
mp3player.cpp:27:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |   scanf("%c %d ", &Z[i], &T[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 292 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 436 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 428 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 340 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 340 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1460 KB Output is correct
2 Correct 12 ms 1420 KB Output is correct
3 Correct 9 ms 1420 KB Output is correct
4 Correct 6 ms 1364 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 1576 KB Output is correct
2 Correct 14 ms 1476 KB Output is correct
3 Correct 12 ms 1560 KB Output is correct
4 Correct 7 ms 1464 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 1684 KB Output is correct
2 Correct 15 ms 1580 KB Output is correct
3 Correct 17 ms 2584 KB Output is correct
4 Correct 7 ms 1552 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 2744 KB Output is correct
2 Correct 24 ms 2776 KB Output is correct
3 Correct 12 ms 2644 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5368 KB Output is correct
2 Correct 36 ms 5492 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 5448 KB Output is correct
2 Correct 38 ms 5452 KB Output is correct