| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 50079 | Benq | Scales (IOI15_scales) | C++14 | 550 ms | 856 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end()
const int MOD = 1000000007;
const ll INF = 1e18;
const int MX = 100001;
/*int num = 0, val[7];
bool cmp(int a, int b) { return val[a] < val[b]; }
int getR(vi a, int b) {
sort(all(a),cmp); return a[b];
}
int getLightest(int A, int B, int C) {
return getR({A,B,C},0);
}
int getHeaviest(int A, int B, int C) {
return getR({A,B,C},2);
}
int getMedian(int A, int B, int C) {
return getR({A,B,C},1);
}
int getNextLightest(int A, int B, int C, int D) {
vi z = {A,B,C}; sort(all(z),cmp);
F0R(i,3) if (cmp(D,z[i])) return z[i];
return z[0];
}
void answer(int* cur) {
F0R(i,6) cout << cur[i] << " ";
cout << "\n";
}*/
#include "scales.h"
void init(int T) {}
vi insEnd(vi cur, int x) {
int t = getMedian(cur[0],cur[2],x);
if (t == cur[0]) cur.insert(cur.begin(),x);
else cur.pb(x);
return cur;
}
vi ins(vi cur, int x) {
int t = getNextLightest(cur[0],cur[sz(cur)/2],cur[sz(cur)-1],x);
if (t == cur[0]) return insEnd(cur,x);
if (t == cur[sz(cur)/2]) {
if (sz(cur) == 3) {
cur.insert(cur.begin()+1,x);
} else {
if (getHeaviest(cur[0],cur[1],x) == x) cur.insert(cur.begin()+2,x);
else cur.insert(cur.begin()+1,x);
}
} else {
if (sz(cur) <= 4) {
cur.insert(cur.begin()+sz(cur)/2+1,x);
} else {
if (getHeaviest(cur[2],cur[3],x) == x) cur.insert(cur.begin()+4,x);
else cur.insert(cur.begin()+3,x);
}
}
return cur;
}
vector<vi> al;
bitset<720> posi;
int eval(int x, vi v, bool b = 0) {
vi VAL(7);
F0R(i,6) {
VAL[al[x][i]] = i;
//if (b) cout << "OOPS " << x << " " << al[x][i] << "\n";
}
/*if (b) {
cout << "OOPS\n";
FOR(i,1,7) cout << val[i] << " ";
cout << "\n";
cout << v[0] << "\n";
}*/
if (v[0] <= 0) {
//if (b) cout << "TT " << VAL[1] << " " << VAL[2] << " " << VAL[3] << " " << VAL[4] << " " << VAL[5] << " " << VAL[6] << " " << v[1] << " " << v[2] << " " << v[3] << " " << VAL[v[1]] << " " << VAL[v[2]] << " " << VAL[v[3]] << "\n";
vi z = {v[1],v[2],v[3]}; sort(all(z),[&VAL](int a, int b) { return VAL[a] < VAL[b]; });
//if (b) cout << "TT " << v[1] << " " << v[2] << " " << v[3] << " " << VAL[v[1]] << " " << VAL[v[2]] << " " << VAL[v[3]] << "\n";
return z[-v[0]];
}
vi z = {v[0],v[1],v[2]}; sort(all(z),[&VAL](int a, int b) { return VAL[a] < VAL[b]; });
F0R(i,3) if (VAL[z[i]] > VAL[v[3]]) return z[i];
return v[0];
}
int test(int a, int b, int c, int d) {
vi co(7);
int mx = 0;
F0R(i,720) if (posi[i]) co[eval(i,{a,b,c,d})] ++;
F0R(i,7) mx = max(mx,co[i]);
return mx;
}
void orderCoins() {
/*FOR(i,1,7) {
int x; cin >> x;
val[x] = i;
}*/
al.clear();
vi z = {1,2,3,4,5,6};
do {
al.pb(z);
} while (next_permutation(all(z)));
F0R(i,720) posi[i] = 1;
pair<int,vi> bes = {MOD,{}};
while (posi.count() > 1) {
//cout << posi.count() << "\n";
FOR(a,1,7) FOR(b,1,7) FOR(c,b+1,7) FOR(d,c+1,7) if (a != b && a != c && a != d)
bes = min(bes,{test(a,b,c,d),{a,b,c,d}});
F0R(z,3) FOR(b,1,7) FOR(c,b+1,7) FOR(d,c+1,7) bes = min(bes,{test(-z,b,c,d),{-z,b,c,d}});
if (bes.s[0] == 0) {
int x = getLightest(bes.s[1],bes.s[2],bes.s[3]);
F0R(i,720) if (posi[i] && eval(i,bes.s) != x) posi[i] = 0;
} else if (bes.s[0] == -1) {
int x = getMedian(bes.s[1],bes.s[2],bes.s[3]);
F0R(i,720) if (posi[i] && eval(i,bes.s) != x) posi[i] = 0;
} else if (bes.s[0] == -2) {
int x = getHeaviest(bes.s[1],bes.s[2],bes.s[3]);
F0R(i,720) if (posi[i] && eval(i,bes.s) != x) posi[i] = 0;
} else {
int x = getNextLightest(bes.s[0],bes.s[1],bes.s[2],bes.s[3]);
F0R(i,720) if (posi[i] && eval(i,bes.s) != x) posi[i] = 0;
}
// break;
}
int* res = new int[6];
F0R(i,720) if (posi[i]) F0R(j,6) res[j] = al[i][j];
answer(res);
}
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||