oj.uz

Submission #885303

# Submission time Handle Problem Language Result Execution time Memory
885303 2023-12-09T12:42:21 Z mgl_diamond Arranging Tickets (JOI17_arranging_tickets) C++17
10 / 100
 247 ms 2504 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 2e5+5;
int n, m, a[N], b[N], c[N];

int cnt[N];
int mx;

void inc(int l, int r, bool t, int val) {
  if (l > r) swap(l, r);
  if (!t) foru(i, l, r-1) cnt[i] += val;
  else {
    foru(i, 1, l-1) cnt[i] += val;
    foru(i, r, n) cnt[i] += val;
  }
}

void solve1() {
	int mn = N;
	for(int mask=0; mask<(1<<m); ++mask) {
    foru(i, 1, n) cnt[i] = 0;
    mx = 0;
    foru(i, 1, m)
      if (mask >> (i-1) & 1) {
        inc(a[i], b[i], 0, 1);
      }
      else {
        inc(a[i], b[i], 1, 1);
      }
    foru(i, 1, n) maximize(mx, cnt[i]);
//    if (mx == 2) {
//      foru(i, 1, n) cout << cnt[i] << " ";
//      cout << "\n";
//    }
    minimize(mn, mx);
	}
	cout << mn;
}

void solve2() {
  foru(i, 1, n) cnt[i] = 0;
  foru(j, 1, m) inc(a[j], b[j], 0, 1);
  vector<int> dir(n+1, 0);
  while (true) {
    bool opt = 1;
    foru(i, 1, m) {
      int lst = *max_element(cnt+1, cnt+n+1);
      inc(a[i], b[i], dir[i], -1);
      inc(a[i], b[i], dir[i]^1, 1);
      int cur = *max_element(cnt+1, cnt+n+1);
      if (cur < lst) {
        dir[i] ^= 1;
        opt = 0;
        break;
      } else {
        inc(a[i], b[i], dir[i]^1, -1);
        inc(a[i], b[i], dir[i], 1);
      }
    }
    if (opt) break;
  }
  cout << *max_element(cnt+1, cnt+n+1);
}

int main() {
	setIO();

	cin >> n >> m;
	foru(i, 1, m) {
		cin >> a[i] >> b[i] >> c[i];
	}
	foru(i, 1, m) {
    while (c[i]-->1) {
      ++m;
      a[m] = a[i];
      b[m] = b[i];
    }
	}

//  solve1(); cout << "\n";
//  solve2();
	if (n <= 20 && m <= 20) solve1();
	else solve2();
}

Compilation message

arranging_tickets.cpp: In function 'void setIO()':
arranging_tickets.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
arranging_tickets.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 2396 KB Output is correct
2 Correct 226 ms 2500 KB Output is correct
3 Correct 223 ms 2396 KB Output is correct
4 Correct 222 ms 2496 KB Output is correct
5 Correct 244 ms 2392 KB Output is correct
6 Correct 220 ms 2396 KB Output is correct
7 Correct 223 ms 2396 KB Output is correct
8 Correct 222 ms 2396 KB Output is correct
9 Correct 220 ms 2492 KB Output is correct
10 Correct 225 ms 2492 KB Output is correct
11 Correct 225 ms 2496 KB Output is correct
12 Correct 247 ms 2492 KB Output is correct
13 Correct 221 ms 2500 KB Output is correct
14 Correct 225 ms 2396 KB Output is correct
15 Correct 230 ms 2504 KB Output is correct

Subtask #2
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 2396 KB Output is correct
2 Correct 226 ms 2500 KB Output is correct
3 Correct 223 ms 2396 KB Output is correct
4 Correct 222 ms 2496 KB Output is correct
5 Correct 244 ms 2392 KB Output is correct
6 Correct 220 ms 2396 KB Output is correct
7 Correct 223 ms 2396 KB Output is correct
8 Correct 222 ms 2396 KB Output is correct
9 Correct 220 ms 2492 KB Output is correct
10 Correct 225 ms 2492 KB Output is correct
11 Correct 225 ms 2496 KB Output is correct
12 Correct 247 ms 2492 KB Output is correct
13 Correct 221 ms 2500 KB Output is correct
14 Correct 225 ms 2396 KB Output is correct
15 Correct 230 ms 2504 KB Output is correct
16 Incorrect 10 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 2396 KB Output is correct
2 Correct 226 ms 2500 KB Output is correct
3 Correct 223 ms 2396 KB Output is correct
4 Correct 222 ms 2496 KB Output is correct
5 Correct 244 ms 2392 KB Output is correct
6 Correct 220 ms 2396 KB Output is correct
7 Correct 223 ms 2396 KB Output is correct
8 Correct 222 ms 2396 KB Output is correct
9 Correct 220 ms 2492 KB Output is correct
10 Correct 225 ms 2492 KB Output is correct
11 Correct 225 ms 2496 KB Output is correct
12 Correct 247 ms 2492 KB Output is correct
13 Correct 221 ms 2500 KB Output is correct
14 Correct 225 ms 2396 KB Output is correct
15 Correct 230 ms 2504 KB Output is correct
16 Incorrect 10 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 2396 KB Output is correct
2 Correct 226 ms 2500 KB Output is correct
3 Correct 223 ms 2396 KB Output is correct
4 Correct 222 ms 2496 KB Output is correct
5 Correct 244 ms 2392 KB Output is correct
6 Correct 220 ms 2396 KB Output is correct
7 Correct 223 ms 2396 KB Output is correct
8 Correct 222 ms 2396 KB Output is correct
9 Correct 220 ms 2492 KB Output is correct
10 Correct 225 ms 2492 KB Output is correct
11 Correct 225 ms 2496 KB Output is correct
12 Correct 247 ms 2492 KB Output is correct
13 Correct 221 ms 2500 KB Output is correct
14 Correct 225 ms 2396 KB Output is correct
15 Correct 230 ms 2504 KB Output is correct
16 Incorrect 10 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 225 ms 2396 KB Output is correct
2 Correct 226 ms 2500 KB Output is correct
3 Correct 223 ms 2396 KB Output is correct
4 Correct 222 ms 2496 KB Output is correct
5 Correct 244 ms 2392 KB Output is correct
6 Correct 220 ms 2396 KB Output is correct
7 Correct 223 ms 2396 KB Output is correct
8 Correct 222 ms 2396 KB Output is correct
9 Correct 220 ms 2492 KB Output is correct
10 Correct 225 ms 2492 KB Output is correct
11 Correct 225 ms 2496 KB Output is correct
12 Correct 247 ms 2492 KB Output is correct
13 Correct 221 ms 2500 KB Output is correct
14 Correct 225 ms 2396 KB Output is correct
15 Correct 230 ms 2504 KB Output is correct
16 Incorrect 10 ms 2396 KB Output isn't correct
17 Halted 0 ms 0 KB -