| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 53928 |
2018-07-01T23:38:31 Z |
Benq |
Scales (IOI15_scales) |
C++14 |
|
306 ms |
1100 KB |
#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;
// GRADER
#include "scales.h"
/*vi VAL = {0,3,2,4,1,5,6};
void answer(int* v) {
F0R(i,6) cout << v[i] << " ";
cout << "\n";
}
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];
}*/
vi val(6);
vector<vi> al;
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 lightest(int A, int B, int C) { return getR({A,B,C},0); }
int heaviest(int A, int B, int C) { return getR({A,B,C},2); }
int median(int A, int B, int C) { return getR({A,B,C},1); }
int nextlightest(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];
}
bool bad(bitset<720> b, int num) {
if (pow(3,num) < b.count()) return 1;
return 0;
}
int eval(int ind, vi v) {
vi VAL = val;
F0R(i,6) val[al[ind][i]] = i;
int z = -1;
if (v[0] == 3) z = nextlightest(v[1],v[2],v[3],v[4]);
if (v[0] == 0) z = lightest(v[1],v[2],v[3]);
if (v[0] == 1) z = median(v[1],v[2],v[3]);
if (v[0] == 2) z = heaviest(v[1],v[2],v[3]);
val = VAL;
return z;
}
struct CMPCMP {
bool operator()(const pair<bitset<720>,int>& l, const pair<bitset<720>,int>& r) const {
F0R(i,720) if (l.f[i] != r.f[i]) return l.f[i] < r.f[i];
return l.s < r.s;
}
};
map<pair<bitset<720>,int>,bool,CMPCMP> good;
vector<bitset<720>> gen(bitset<720> b, vi v) {
bitset<720> tmp[6];
F0R(i,720) if (b[i]) tmp[eval(i,v)][i] = 1;
vector<bitset<720>> ans;
F0R(i,6) if (tmp[i].count()) ans.pb(tmp[i]);
return ans;
}
bool guarantee(bitset<720> b, int num) {
if (b.count() == 1) return 1;
if (bad(b,num)) return 0;
if (good.count({b,num})) return good[{b,num}];
F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) F0R(l,6) if (l != i && l != j && l != k) {
vector<bitset<720>> v = gen(b,{3,i,j,k,l});
bool tri = 1;
for (auto a: v) if (bad(a,num-1)) {
tri = 0;
break;
}
if (tri) {
for (auto a: v) if (!guarantee(a,num-1)) {
tri = 0;
break;
}
if (tri) {
/*if (b.count() >= 80) {
for (auto a: v) cout << "ZZ " << b.count() << " " << a.count() << " " << good[{a,num-1}] << " " << a << "\n";
}*/
return good[{b,num}] = 1;
}
}
}
F0R(z,3) F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) {
vector<bitset<720>> v = gen(b,{z,i,j,k});
bool tri = 1;
for (auto a: v) if (bad(a,num-1)) {
tri = 0;
break;
}
if (tri) {
for (auto a: v) if (!guarantee(a,num-1)) {
tri = 0;
break;
}
if (tri) {
return good[{b,num}] = 1;
}
}
}
return good[{b,num}] = 0;
}
void init(int T) {
al.clear();
vi z = {0,1,2,3,4,5};
do {
al.pb(z);
} while (next_permutation(all(z)));
bitset<720> x; F0R(i,720) x[i] = 1;
guarantee(x,6);
}
void solve(bitset<720> b, int num) {
if (b.count() == 1) {
F0R(i,720) if (b[i]) {
int vv[6];
F0R(j,6) vv[j] = al[i][j]+1;
answer(vv);
}
return;
}
if (!good.count({b,num})) {
cout << "OOPS " << b.count() << " " << num << " " << b << "\n";
return;
}
F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) F0R(l,6) if (l != i && l != j && l != k) {
vector<bitset<720>> v = gen(b,{3,i,j,k,l});
bool tri = 1;
for (auto a: v) if (!good.count({a,num-1}) || good[{a,num-1}] == 0) {
tri = 0;
break;
}
if (tri) {
/*cout << "HUH " << i << " " << j << " " << k << " " << l << "\n";
for (auto a: v) cout << a.count() << " ";
cout << "\n";*/
if (tri) {
int x = getNextLightest(i+1,j+1,k+1,l+1)-1;
bitset<720> B;
F0R(I,720) {
// cout << eval(I,{0,i,j,k,l}) << "\n";
if (b[I] && eval(I,{3,i,j,k,l}) == x) B[I] = 1;
}
solve(B,num-1);
return;
}
}
}
F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) {
vector<bitset<720>> v = gen(b,{0,i,j,k});
bool tri = 1;
for (auto a: v) if (bad(a,num-1)) {
tri = 0;
break;
}
if (tri) {
for (auto a: v) if (!guarantee(a,num-1)) {
tri = 0;
break;
}
if (tri) {
int x = getLightest(i+1,j+1,k+1)-1;
bitset<720> B;
F0R(I,720) {
// cout << eval(I,{0,i,j,k,l}) << "\n";
if (b[I] && eval(I,{0,i,j,k}) == x) B[I] = 1;
}
solve(B,num-1);
return;
}
}
}
F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) {
vector<bitset<720>> v = gen(b,{1,i,j,k});
bool tri = 1;
for (auto a: v) if (bad(a,num-1)) {
tri = 0;
break;
}
if (tri) {
for (auto a: v) if (!guarantee(a,num-1)) {
tri = 0;
break;
}
if (tri) {
int x = getMedian(i+1,j+1,k+1)-1;
bitset<720> B;
F0R(I,720) {
// cout << eval(I,{0,i,j,k,l}) << "\n";
if (b[I] && eval(I,{1,i,j,k}) == x) B[I] = 1;
}
solve(B,num-1);
return;
}
}
}
F0R(i,6) FOR(j,i+1,6) FOR(k,j+1,6) {
vector<bitset<720>> v = gen(b,{2,i,j,k});
bool tri = 1;
for (auto a: v) if (bad(a,num-1)) {
tri = 0;
break;
}
if (tri) {
for (auto a: v) if (!guarantee(a,num-1)) {
tri = 0;
break;
}
if (tri) {
int x = getHeaviest(i+1,j+1,k+1)-1;
bitset<720> B;
F0R(I,720) {
// cout << eval(I,{0,i,j,k,l}) << "\n";
if (b[I] && eval(I,{2,i,j,k}) == x) B[I] = 1;
}
solve(B,num-1);
return;
}
}
}
}
void orderCoins() {
bitset<720> b; F0R(i,720) b[i] = 1;
solve(b,6);
}
/*int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
init(1);
orderCoins();
orderCoins();
}*/
// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS
Compilation message
In file included from grader.c:2:0:
graderlib.c: In function 'void answer(int*)':
graderlib.c:53:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
if (_ghksjhdfkae19ga_ > 1)
^~
graderlib.c:56:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
for (i = 0; i < 6; i++) {
^~~
scales.cpp: In function 'bool bad(std::bitset<720>, int)':
scales.cpp:81:29: warning: conversion to '__gnu_cxx::__promote_2<int, int, double, double>::__type {aka double}' from 'std::size_t {aka long unsigned int}' may alter its value [-Wconversion]
if (pow(3,num) < b.count()) return 1;
~~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:158:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
257 ms |
600 KB |
Output is correct |
| 2 |
Correct |
226 ms |
628 KB |
Output is correct |
| 3 |
Correct |
228 ms |
680 KB |
Output is correct |
| 4 |
Correct |
254 ms |
680 KB |
Output is correct |
| 5 |
Correct |
244 ms |
788 KB |
Output is correct |
| 6 |
Correct |
238 ms |
788 KB |
Output is correct |
| 7 |
Correct |
241 ms |
876 KB |
Output is correct |
| 8 |
Correct |
237 ms |
876 KB |
Output is correct |
| 9 |
Correct |
277 ms |
876 KB |
Output is correct |
| 10 |
Correct |
306 ms |
1040 KB |
Output is correct |
| 11 |
Correct |
240 ms |
1040 KB |
Output is correct |
| 12 |
Correct |
263 ms |
1040 KB |
Output is correct |
| 13 |
Correct |
231 ms |
1040 KB |
Output is correct |
| 14 |
Correct |
232 ms |
1040 KB |
Output is correct |
| 15 |
Correct |
267 ms |
1040 KB |
Output is correct |
| 16 |
Correct |
228 ms |
1040 KB |
Output is correct |
| 17 |
Correct |
241 ms |
1040 KB |
Output is correct |
| 18 |
Correct |
227 ms |
1040 KB |
Output is correct |
| 19 |
Correct |
232 ms |
1040 KB |
Output is correct |
| 20 |
Correct |
289 ms |
1060 KB |
Output is correct |
| 21 |
Correct |
230 ms |
1060 KB |
Output is correct |
| 22 |
Correct |
234 ms |
1060 KB |
Output is correct |
| 23 |
Correct |
246 ms |
1060 KB |
Output is correct |
| 24 |
Correct |
284 ms |
1060 KB |
Output is correct |
| 25 |
Correct |
262 ms |
1060 KB |
Output is correct |
| 26 |
Correct |
260 ms |
1060 KB |
Output is correct |
| 27 |
Correct |
272 ms |
1092 KB |
Output is correct |
| 28 |
Correct |
256 ms |
1092 KB |
Output is correct |
| 29 |
Correct |
266 ms |
1092 KB |
Output is correct |
| 30 |
Correct |
249 ms |
1092 KB |
Output is correct |
| 31 |
Correct |
265 ms |
1092 KB |
Output is correct |
| 32 |
Correct |
269 ms |
1092 KB |
Output is correct |
| 33 |
Correct |
227 ms |
1092 KB |
Output is correct |
| 34 |
Correct |
235 ms |
1092 KB |
Output is correct |
| 35 |
Correct |
226 ms |
1092 KB |
Output is correct |
| 36 |
Correct |
228 ms |
1092 KB |
Output is correct |
| 37 |
Correct |
227 ms |
1092 KB |
Output is correct |
| 38 |
Correct |
238 ms |
1100 KB |
Output is correct |
| 39 |
Correct |
287 ms |
1100 KB |
Output is correct |
| 40 |
Correct |
289 ms |
1100 KB |
Output is correct |
