oj.uz

답안 #125281

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
125281 2019-07-05T04:08:18 Z 조승현(#3064) Arranging Tickets (JOI17_arranging_tickets) C++14
0 / 100
 1180 ms 476 KB 
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, C[3010], S[3010], CK[3010];
struct point {
	int a, b;
}w[3010];
bool Pos(int K) {
	int i, j;
	for (i = 1; i <= n; i++)C[i] = 0;
	for (i = 1; i <= m; i++) {
		for (j = w[i].a; j < w[i].b; j++)C[j]++;
	}
	for (j = 0; j < 50000000 / max(n, m); j++) {
		int Mx = 0, ss = 0;
		S[0] = 0;
		for (i = 1; i <= n; i++) {
			S[i] = S[i - 1] + (C[i] >= K);
			ss += (C[i] > K);
		}
		if (ss == 0)return true;
		int MM = -1, pv = -1;
		for (i = 1; i <= m; i++) {
			int t = S[w[i].b - 1] - S[w[i].a - 1];
			if (CK[i])t = S[n] - t;
			if (MM < t)MM = t, pv = i;
		}
		for (i = 1; i <= n; i++) {
			if ((CK[pv] == 0) == (w[pv].a <= i && i < w[pv].b)) C[i]--;
			else C[i]++;
		}
		CK[pv] ^= 1;
	}
	return false;
}
int main() {
	int i, j;
	scanf("%d%d", &n, &m);
	if (n > 3000 || m > 3000)return 0;
	for (i = 1; i <= m; i++) {
		int t;
		scanf("%d%d%d", &w[i].a, &w[i].b, &t);
		if (w[i].a > w[i].b)swap(w[i].a, w[i].b);
	}
	int res = 1e9;
	int b = 1, e = m, mid, r;
	while (b <= e) {
		mid = (b + e) >> 1;
		if (Pos(mid)) {
			r = mid;
			e = mid - 1;
		}
		else b = mid + 1;
	}
	printf("%d\n", r);
}

Compilation message

arranging_tickets.cpp: In function 'int main()':
arranging_tickets.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~
arranging_tickets.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &w[i].a, &w[i].b, &t);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1180 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1180 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1180 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1180 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1180 ms 476 KB Output isn't correct
2 Halted 0 ms 0 KB -