Submission #288000

#	Time	Username	Problem	Language	Result	Execution time	Memory
288000		kevlee	Scales (IOI15_scales)	C++17	72.92 / 100	336 ms	504 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mod 1000000007
#define h1 7897897897897897
#define h2 7897466719774591
#define b1 98762051
#define b2 98765431
#define inf 1000000000
#define pi 3.1415926535897932384626
#define LMAX 9223372036854775807
#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pii>
#define SET(a, b) memset(a, b, sizeof(a));
#define all(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FORD(i, a, b) for (int i = (a); i >= (b); i--)
int a[10], pos[10], id, remain;
bool dead[1000];
void init(int T) {
  return;
}
void setup() {
  FOR(i, 1, 6) a[i] = i;
  id = 0;
}
void updateLightest(int A, int B, int C) { // A is lightest
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if (pos[A] > pos[B] || pos[A] > pos[C]) {
      dead[id] = true;
      remain--;
    }
  } while (next_permutation(a+1, a+7));
}
int Lightest(int A, int B, int C) { // A is lightest
  int cnt = 0;
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if (pos[A] > pos[B] || pos[A] > pos[C]) {
      cnt++;
    }
  } while (next_permutation(a+1, a+7));
  return cnt;
}
void updateMedian(int A, int B, int C) { // A is median
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if ((pos[A] < pos[B] && pos[A] > pos[C]) || (pos[A] > pos[B] && pos[A] < pos[C])) {}
    else {
      dead[id] = true;
      remain--;
    }
  } while (next_permutation(a+1, a+7));
}
int Median(int A, int B, int C) { // A is median
  int cnt = 0;
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if ((pos[A] < pos[B] && pos[A] > pos[C]) || (pos[A] > pos[B] && pos[A] < pos[C])) {}
    else {
      cnt++;
    }
  } while (next_permutation(a+1, a+7));
  return cnt;
}
void updateHeaviest(int A, int B, int C) { // A is heaviest
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if (pos[A] < pos[B] || pos[A] < pos[C]) {
      dead[id] = true;
      remain--;
    }
  } while (next_permutation(a+1, a+7));
}
int Heaviest(int A, int B, int C) { // A is heaviest
  int cnt = 0;
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if (pos[A] < pos[B] || pos[A] < pos[C]) {
      cnt++;
    }
  } while (next_permutation(a+1, a+7));
  return cnt;
}
void updateNextLightest(int A, int B, int C, int D) { //A is next lightest
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if (pos[D] > pos[A] && pos[D] > pos[B] && pos[D] > pos[C]) {
      if (!(pos[A] < pos[B] && pos[A] < pos[C])) {
        dead[id] = true;
        remain--;
      }
    } else {
      int correct = inf, minn = inf;
      if (pos[A] > pos[D] && pos[A] < minn) {
        minn = pos[A];
        correct = A;
      }
      if (pos[B] > pos[D] && pos[B] < minn) {
        minn = pos[B];
        correct = B;
      }
      if (pos[C] > pos[D] && pos[C] < minn) {
        minn = pos[C];
        correct = C;
      }
      if (correct != A) {
        dead[id] = true;
        remain--;
      }
    }
  } while (next_permutation(a+1, a+7));
}
int NextLightest(int A, int B, int C, int D) { //A is next lightest
  int cnt = 0;
  setup();
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 1, 6) pos[a[i]] = i;
    if (pos[D] > pos[A] && pos[D] > pos[B] && pos[D] > pos[C]) {
      if (!(pos[A] < pos[B] && pos[A] < pos[C])) {
        cnt++;
      }
    } else {
      int correct = inf, minn = inf;
      if (pos[A] > pos[D] && pos[A] < minn) {
        minn = pos[A];
        correct = A;
      }
      if (pos[B] > pos[D] && pos[B] < minn) {
        minn = pos[B];
        correct = B;
      }
      if (pos[C] > pos[D] && pos[C] < minn) {
        minn = pos[C];
        correct = C;
      }
      if (correct != A) {
        cnt++;
      }
    }
  } while (next_permutation(a+1, a+7));
  return cnt;
}
void orderCoins() {
  remain = 720;
  FOR(i, 1, 720) dead[i] = false;
  while (remain > 1) {
    int qa = -1, qb = -1, qc = -1, qd = -1, maxx = 0, mode = -1;
    FOR(A, 1, 6) {
      FOR(B, A+1, 6) {
        FOR(C, B+1, 6) {
          int t = min(Lightest(A, B, C), min(Lightest(B, A, C), Lightest(C, A, B)));
          if (t > maxx) {
            maxx = t;
            mode = 1;
            qa = A;
            qb = B;
            qc = C;
          }
          t = min(Median(A, B, C), min(Median(B, A, C), Median(C, A, B)));
          if (t > maxx) {
            maxx = t;
            mode = 2;
            qa = A;
            qb = B;
            qc = C;
          }
          t = min(Heaviest(A, B, C), min(Heaviest(B, A, C), Heaviest(C, A, B)));
          if (t > maxx) {
            maxx = t;
            mode = 3;
            qa = A;
            qb = B;
            qc = C;
          }
          FOR(D, C+1, 6) {
            t = min(NextLightest(B, C, D, A), min(NextLightest(C, B, D, A), NextLightest(D, B, C, A)));
            if (t > maxx) {
              maxx = t;
              mode = 4;
              qa = B;
              qb = C;
              qc = D;
              qd = A;
            }
            t = min(NextLightest(A, C, D, B), min(NextLightest(C, A, D, B), NextLightest(D, A, C, B)));
            if (t > maxx) {
              maxx = t;
              mode = 4;
              qa = A;
              qb = C;
              qc = D;
              qd = B;
            }
            t = min(NextLightest(A, B, D, C), min(NextLightest(B, A, D, C), NextLightest(D, A, B, C)));
            if (t > maxx) {
              maxx = t;
              mode = 4;
              qa = A;
              qb = B;
              qc = D;
              qd = C;
            }
            t = min(NextLightest(A, B, C, D), min(NextLightest(B, A, C, D), NextLightest(C, A, B, D)));
            if (t > maxx) {
              maxx = t;
              mode = 4;
              qa = A;
              qb = B;
              qc = C;
              qd = D;
            }
          }
        }
      }
    }
    if (mode == 1) {
      int res = getLightest(qa, qb, qc);
      if (res == qa) updateLightest(qa, qb, qc);
      else if (res == qb) updateLightest(qb, qa, qc);
      else updateLightest(qc, qa, qb);
    } else if (mode == 2) {
      int res = getMedian(qa, qb, qc);
      if (res == qa) updateMedian(qa, qb, qc);
      else if (res == qb) updateMedian(qb, qa, qc);
      else updateMedian(qc, qa, qb);
    } else if (mode == 3) {
      int res = getHeaviest(qa, qb, qc);
      if (res == qa) updateHeaviest(qa, qb, qc);
      else if (res == qb) updateHeaviest(qb, qa, qc);
      else updateHeaviest(qc, qa, qb);
    } else {
      int res = getNextLightest(qa, qb, qc, qd);
      if (res == qa) updateNextLightest(qa, qb, qc, qd);
      else if (res == qb) updateNextLightest(qb, qa, qc, qd);
      else updateNextLightest(qc, qa, qb, qd);
      //cout << "res = " << res << endl;
    }
    //cout << mode << ' ' << qa << ' ' << qb  << ' ' << qc << ' ' << qd << endl;
    //cout << remain << endl;
  }
  setup();
  int ans[6];
  do {
    id++;
    if (dead[id]) continue;
    FOR(i, 0, 5) ans[i] = a[i + 1];
    answer(ans);
  } while (next_permutation(a+1, a+7));
}

Compilation message (stderr)

scales.cpp: In function 'void init(int)':
scales.cpp:27:15: warning: unused parameter 'T' [-Wunused-parameter]
   27 | void init(int T) {
      |           ~~~~^

• Subtask 1: 72.916667 / 100