| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 755628 | Theo830 | Scales (IOI15_scales) | C++17 | 147 ms | 460 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>
using namespace std;
typedef int ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "scales.h"
/*
#define _MAXN 6
#define _MAX_ANSWER_CALLS 1
static int _realC[_MAXN];
static int _ind[_MAXN];
static int _numQueries;
static int _numAnswerCalls;
static void _initNewTest() {
int i, ret;
for (i = 0; i < _MAXN; i++) {
cin>>_realC[i];
_realC[i]--;
_ind[_realC[i]] = i;
}
_numQueries = 0;
_numAnswerCalls = 0;
}
void answer(int W[]) {
int i;
_numAnswerCalls++;
if (_numAnswerCalls > _MAX_ANSWER_CALLS)
return;
for (i = 0; i < 6; i++)
cout<<W[i]<<" ";
cout<<"\n";
cout<<_numQueries<<"\n";
}
static void _checkQuery(int A, int B, int C, int D) {
if (D == -1) {
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6)
assert(0);
if (A == B || B == C || A == C)
assert(0);
}
else {
if (A < 1 || A > 6 || B < 1 || B > 6 || C < 1 || C > 6 || D < 1 || D > 6)
assert(0);
if (A == B || A == C || A == D || B == C || B == D || C == D)
assert(0);
}
}
int getMedian(int A, int B, int C) {
_numQueries++;
_checkQuery(A, B, C, -1);
A--; B--; C--;
if (_ind[B] < _ind[A] && _ind[A] < _ind[C])
return A + 1;
if (_ind[C] < _ind[A] && _ind[A] < _ind[B])
return A + 1;
if (_ind[A] < _ind[B] && _ind[B] < _ind[C])
return B + 1;
if (_ind[C] < _ind[B] && _ind[B] < _ind[A])
return B + 1;
return C + 1;
}
int getHeaviest(int A, int B, int C) {
_numQueries++;
_checkQuery(A, B, C, -1);
A--; B--; C--;
if (_ind[A] > _ind[B] && _ind[A] > _ind[C])
return A + 1;
if (_ind[B] > _ind[A] && _ind[B] > _ind[C])
return B + 1;
return C + 1;
}
int getLightest(int A, int B, int C) {
_numQueries++;
_checkQuery(A, B, C, -1);
A--; B--; C--;
if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
return A + 1;
if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
return B + 1;
return C + 1;
}
int getNextLightest(int A, int B, int C, int D) {
int allLess = 1;
_numQueries++;
_checkQuery(A, B, C, D);
A--; B--; C--; D--;
if (_ind[A] > _ind[D] || _ind[B] > _ind[D] || _ind[C] > _ind[D])
allLess = 0;
if (allLess == 1) {
if (_ind[A] < _ind[B] && _ind[A] < _ind[C])
return A + 1;
if (_ind[B] < _ind[A] && _ind[B] < _ind[C])
return B + 1;
return C + 1;
}
if (_ind[A] > _ind[D]) {
if ((_ind[A] < _ind[B] || _ind[B] < _ind[D]) && (_ind[A] < _ind[C] || _ind[C] < _ind[D]))
return A + 1;
}
if (_ind[B] > _ind[D]) {
if ((_ind[B] < _ind[A] || _ind[A] < _ind[D]) && (_ind[B] < _ind[C] || _ind[C] < _ind[D]))
return B + 1;
}
return C + 1;
}
*/
void init(int T) {
}
void orderCoins() {
int W[] = {1, 2, 3, 4, 5, 6};
vector<int>P;
f(i,0,6){
P.pb(i+1);
}
set<vector<int> >ex;
do{
ex.insert(P);
}
while(next_permutation(all(P)));
while(ex.size() > 1){
ll t = 0,a,b,c,d,ans = 0;
f(i,0,6){
f(j,i+1,6){
f(k,j+1,6){
ll res = INF;
ll cur = 0;
for(auto x:ex){
if(x[i] < x[j] && x[i] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[j] < x[i] && x[j] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[k] < x[i] && x[k] < x[j]){
}
else{
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 0;
a = i;
b = j;
c = k;
}
}
}
}
f(i,0,6){
f(j,i+1,6){
f(k,j+1,6){
ll res = INF;
ll cur = 0;
for(auto x:ex){
if(x[i] < x[j] && x[i] > x[k]){
}
else if(x[i] > x[j] && x[i] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[k] < x[j] && x[k] > x[i]){
}
else if(x[k] > x[j] && x[k] < x[i]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[j] < x[i] && x[j] > x[k]){
}
else if(x[j] > x[i] && x[j] < x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 1;
a = i;
b = j;
c = k;
}
}
}
}
f(i,0,6){
f(j,i+1,6){
f(k,j+1,6){
ll res = INF;
ll cur = 0;
for(auto x:ex){
if(x[i] > x[j] && x[i] > x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[j] > x[i] && x[j] > x[k]){
}
else{
cur++;
}
}
res = min(res,cur);
cur = 0;
for(auto x:ex){
if(x[k] > x[i] && x[k] > x[j]){
}
else{
cur++;
}
}
res = min(res,cur);
if(ans < res){
ans = res;
t = 2;
a = i;
b = j;
c = k;
}
}
}
}
a++;
b++;
c++;
set<vector<int> >fkale;
if(t == 0){
ll pos = getLightest(a,b,c);
a--;
b--;
c--;
pos--;
for(auto x:ex){
if(x[pos] <= x[a] && x[pos] <= x[b] && x[pos] <= x[c]){
}
else{
fkale.insert(x);
}
}
}
else if(t == 1){
ll pos = getMedian(a,b,c);
a--;
b--;
c--;
pos--;
for(auto x:ex){
ll posoi = (x[pos] > x[a]) + (x[pos] > x[b]) + (x[pos] > x[c]);
if(posoi != 1){
fkale.insert(x);
}
}
}
else if(t == 2){
ll pos = getHeaviest(a,b,c);
a--;
b--;
c--;
pos--;
for(auto x:ex){
if(x[pos] >= x[a] && x[pos] >= x[b] && x[pos] >= x[c]){
}
else{
fkale.insert(x);
}
}
}
else{
}
for(auto x:fkale){
ex.erase(x);
}
}
vll a = (*ex.begin());
f(i,0,6){
W[a[i]-1] = i+1;
}
answer(W);
}
/*
int main() {
int T, i;
cin>>T;
init(T);
for (i = 1; i <= T; i++) {
_initNewTest();
orderCoins();
}
return 0;
}
*/
Compilation message (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||