| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 230355 |
2020-05-09T16:55:48 Z |
CaroLinda |
Scales (IOI15_scales) |
C++14 |
|
88 ms |
504 KB |
#include <bits/stdc++.h>
#include "scales.h"
#define pb push_back
#define mk make_pair
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define ll long long
#define debug printf
#define max3(a,b,c) max( a , max(b,c) )
using namespace std ;
int pot[10] ;
int cool[ 1500 ];
bool ended[1500] ;
vector< vector<int> > permutacoes ;
vector< pair<int, vector<int> > > operacoes ;
int get_pos(int pos )
{
if( ended[pos] ) return cool[pos] ;
pair<int, vector<int> > op = operacoes[ cool[pos] ] ;
int resp ;
if( op.ff == 1 ) resp = getLightest( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1 ) ;
else if( op.ff == 2 ) resp = getMedian( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1 ) ;
else if( op.ff == 3 ) resp = getHeaviest( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1 ) ;
else resp = getNextLightest( op.ss[0] + 1 , op.ss[1] + 1 ,op.ss[2] + 1, op.ss[3] + 1 ) ;
lp(i,0,3)
if( resp == op.ss[i]+1 ) return get_pos( pos*3 + i ) ;
}
bool solve(int pos , int steps_left , vector<int> possible )
{
if( possible.size() <= 1 )
{
if( possible.size() == 1 )
cool[pos] = possible[0] , ended[pos] = true ;
return true ;
}
for(int g = 0 ; g < (int)operacoes.size() ; g++ )
{
auto op = operacoes[g] ;
bool ok = true ;
vector<int> ans[3];
for(auto p : possible )
{
int x = permutacoes[p][ op.ss[0] ] ;
int y = permutacoes[p][ op.ss[1] ] ;
int z = permutacoes[p][ op.ss[2] ] ;
int val[3] = {x,y,z} , decode[6] ;
sort(val,val+3) ;
decode[x] = 0 ;
decode[y] = 1 ;
decode[z] = 2 ;
if(op.ff == 1) ans[ decode[ val[0] ] ].pb(p) ;
else if(op.ff == 2) ans[ decode[ val[1] ] ].pb(p) ;
else if(op.ff == 3) ans[ decode[ val[2] ] ].pb(p) ;
else
{
int w = permutacoes[p][ op.ss[3] ] ;
if( w < val[0] || w > val[2] ) ans[ decode[ val[0] ] ].pb(p) ;
else if ( w < val[1] ) ans[ decode[ val[1] ] ].pb(p) ;
else ans[ decode[ val[2] ] ].pb(p) ;
}
}
if( (int)max( ans[0].size() , max( ans[1].size() , ans[2].size() ) ) > pot[steps_left-1] )
continue ;
lp(j,0,3)
ok &= solve(pos*3 + j , steps_left - 1 , ans[j] ) ;
if(ok)
{
cool[pos] = g ;
return true ;
}
}
return false ;
}
bool isOn(int i, int m) { return ((1<<i)&m)!= 0 ; }
void init(int T)
{
pot[0] = 1 ;
for(int i = 1 ; i < 7 ; i++ ) pot[i] = 3*pot[i-1] ;
vector<int> v(6) ;
iota(all(v) , 0 ) ;
do{
permutacoes.pb(v) ;
} while( next_permutation(all(v)) ) ;
vector<int> lista( permutacoes.size() ) ;
iota(all(lista), 0 ) ;
for(int i = 0 ; i < (1<<6) ; i++ )
{
if( __builtin_popcount(i) != 3 ) continue ;
vector<int> ligado ;
for(int j = 0 ; j < 6 ; j++ )
if( isOn(j,i) ) ligado.pb(j) ;
lp(j,1,4) operacoes.pb( mk( j , ligado ) ) ;
lp(j,0,6)
if(!isOn(j,i))
{
ligado.pb(j) ;
operacoes.pb( mk( 4 , ligado ) );
ligado.pop_back() ;
}
}
solve( 1 , 6 , lista ) ;
}
void orderCoins() {
int pos = get_pos( 1 ) ;
int W[6] ;
lp(i,0,6) W[ permutacoes[pos][i] ] = i+1 ;
answer(W) ;
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:111:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T)
^
scales.cpp: In function 'int get_pos(int)':
scales.cpp:41:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
384 KB |
Output is correct |
| 2 |
Correct |
73 ms |
384 KB |
Output is correct |
| 3 |
Correct |
74 ms |
384 KB |
Output is correct |
| 4 |
Correct |
74 ms |
384 KB |
Output is correct |
| 5 |
Correct |
73 ms |
464 KB |
Output is correct |
| 6 |
Correct |
75 ms |
384 KB |
Output is correct |
| 7 |
Correct |
76 ms |
504 KB |
Output is correct |
| 8 |
Correct |
75 ms |
404 KB |
Output is correct |
| 9 |
Correct |
74 ms |
384 KB |
Output is correct |
| 10 |
Correct |
74 ms |
432 KB |
Output is correct |
| 11 |
Correct |
75 ms |
384 KB |
Output is correct |
| 12 |
Correct |
76 ms |
384 KB |
Output is correct |
| 13 |
Correct |
74 ms |
384 KB |
Output is correct |
| 14 |
Correct |
74 ms |
384 KB |
Output is correct |
| 15 |
Correct |
75 ms |
504 KB |
Output is correct |
| 16 |
Correct |
75 ms |
384 KB |
Output is correct |
| 17 |
Correct |
74 ms |
384 KB |
Output is correct |
| 18 |
Correct |
74 ms |
384 KB |
Output is correct |
| 19 |
Correct |
76 ms |
384 KB |
Output is correct |
| 20 |
Correct |
75 ms |
384 KB |
Output is correct |
| 21 |
Correct |
73 ms |
384 KB |
Output is correct |
| 22 |
Correct |
88 ms |
436 KB |
Output is correct |
| 23 |
Correct |
75 ms |
384 KB |
Output is correct |
| 24 |
Correct |
74 ms |
384 KB |
Output is correct |
| 25 |
Correct |
74 ms |
384 KB |
Output is correct |
| 26 |
Correct |
74 ms |
384 KB |
Output is correct |
| 27 |
Correct |
77 ms |
504 KB |
Output is correct |
| 28 |
Correct |
77 ms |
384 KB |
Output is correct |
| 29 |
Correct |
74 ms |
384 KB |
Output is correct |
| 30 |
Correct |
78 ms |
384 KB |
Output is correct |
| 31 |
Correct |
74 ms |
384 KB |
Output is correct |
| 32 |
Correct |
76 ms |
384 KB |
Output is correct |
| 33 |
Correct |
78 ms |
432 KB |
Output is correct |
| 34 |
Correct |
74 ms |
384 KB |
Output is correct |
| 35 |
Correct |
77 ms |
384 KB |
Output is correct |
| 36 |
Correct |
73 ms |
384 KB |
Output is correct |
| 37 |
Correct |
75 ms |
384 KB |
Output is correct |
| 38 |
Correct |
74 ms |
384 KB |
Output is correct |
| 39 |
Correct |
77 ms |
384 KB |
Output is correct |
| 40 |
Correct |
77 ms |
504 KB |
Output is correct |
