Submission #875374

#	Time	Username	Problem	Language	Result	Execution time	Memory
875374		mgl_diamond	Just Long Neckties (JOI20_ho_t1)	C++17	100 / 100	153 ms	12064 KiB

ho_t1

#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, a[N], b[N], ret[N];

int f[1<<21];

void solve1() {
  memset(ret, 0x3f, sizeof(ret));
  memset(f, 0x3f, sizeof(f));
  f[0] = 0;
  int full = (1<<(n+1))-1;
  foru(i, 0, full) {
    int cnt = __builtin_popcount(i)+1, zero;
    foru(j, 0, n) if (!(i >> j & 1)) {
      minimize(f[i+(1<<j)], max(f[i], a[j+1]-b[cnt]));
      zero = j+1;
    }
    if (cnt == n+1) {
      minimize(ret[zero], f[i]);
    }
  }
  foru(i, 1, n+1) {
    cout << ret[i] << " ";
  } cout << "\n";
}

void solve2() {
  sort(b+1, b+n+1);
  foru(i, 1, n+1) {
    vector<int> tmp;
    foru(j, 1, n+1) if (i^j) tmp.push_back(a[j]);
    sort(all(tmp));
    int ans = 0;
    foru(i, 1, n) maximize(ans, tmp[i-1] - b[i]);
    cout << ans << " "; 
  } cout << "\n";
}

void solve3() {
  vector<int> idx;
  foru(i, 1, n+1) idx.push_back(i);
  sort(all(idx), [&](int x, int y){ return a[x] < a[y]; });
  sort(b+1, b+n+1);

  vector<int> suff(n+1);
  ford(i, n-1, 1) {
    suff[i] = suff[i+1];
    maximize(suff[i], a[idx[i]]-b[i]);
  }

  int cur_max = 0;
  foru(i, 1, n) {
    ret[idx[i-1]] = cur_max;
    maximize(ret[idx[i-1]], suff[i]);
    maximize(ret[idx[i-1]], a[idx[n]] - b[n]);
    maximize(cur_max, a[idx[i-1]] - b[i]);
  }

  ret[idx[n]] = cur_max;
  foru(i, 1, n+1) cout << ret[i] << " "; cout << "\n";
}

int main() {
  setIO();

  cin >> n;
  foru(i, 1, n+1) cin >> a[i];
  foru(i, 1, n) cin >> b[i];

  // solve1();
  // solve2();
  // solve3();
  if (n <= 20) solve1();
  else if (n <= 2000) solve2();
  else solve3();
}

Compilation message (stderr)

ho_t1.cpp: In function 'void solve3()':
ho_t1.cpp:6:23: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    6 | #define foru(i, l, r) for(int i=(l); i<=(r); ++i)
      |                       ^~~
ho_t1.cpp:85:3: note: in expansion of macro 'foru'
   85 |   foru(i, 1, n+1) cout << ret[i] << " "; cout << "\n";
      |   ^~~~
ho_t1.cpp:85:42: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   85 |   foru(i, 1, n+1) cout << ret[i] << " "; cout << "\n";
      |                                          ^~~~
ho_t1.cpp: In function 'void setIO()':
ho_t1.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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t1.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);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t1.cpp: In function 'void solve1()':
ho_t1.cpp:15:61: warning: 'zero' may be used uninitialized in this function [-Wmaybe-uninitialized]
   15 | template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
      |                                                           ~~^~~
ho_t1.cpp:38:40: note: 'zero' was declared here
   38 |     int cnt = __builtin_popcount(i)+1, zero;
      |                                        ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91