| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 48986 |
2018-05-21T06:08:54 Z |
Namnamseo |
Scales (IOI15_scales) |
C++17 |
|
639 ms |
1012 KB |
#include "scales.h"
#include <algorithm>
#include <vector>
#include <functional>
using namespace std;
int lst[720][6];
void init(int T) {
int cur[6];
for(int i=0; i<6; ++i) cur[i]=i+1;
int ind=0;
do {
for(int i=0; i<6; ++i) lst[ind][i]=cur[i];
++ind;
} while(next_permutation(cur, cur+6));
}
inline int f1(int a,int b,int c){ return max(a, max(b, c)); }
inline int f2(int a,int b,int c){ return min(a, min(b, c)); }
inline int f3(int a,int b,int c){ return a+b+c-f1(a,b,c)-f2(a,b,c); }
inline int f4(int a,int b,int c,int d){
int t;
if((t=f1(a,b,c))<d) return f2(a,b,c);
else {
int u=f2(a,b,c);
int v=a+b+c-t-u;
if(v<d) return t;
if(u<d) return v;
return u;
}
}
int maxdiff(vector<int>& av,vector<int>& bv,vector<int>& cv){
int a=av.size(), b=bv.size(), c=cv.size();
if(a>b) swap(a,b);
if(b>c) swap(b,c);
if(a>b) swap(a,b);
return c;
}
struct func_obj{
int type, a, b, c, d;
};
tuple<vector<int>,vector<int>,vector<int>> getAppliedStates(vector<int>& states,int type,int a,int b,int c,int d){
vector<int> x,y,z;
for(int s:states){
int ret=0;
if(type==1) ret=f1(lst[s][a],lst[s][b],lst[s][c]);
else if(type==2) ret=f2(lst[s][a],lst[s][b],lst[s][c]);
else if(type==3) ret=f3(lst[s][a],lst[s][b],lst[s][c]);
else if(type==4) ret=f4(lst[s][a],lst[s][b],lst[s][c],lst[s][d]);
if(ret == lst[s][a]) x.push_back(s);
else if(ret == lst[s][b]) y.push_back(s);
else z.push_back(s);
}
return tuple<vector<int>,vector<int>,vector<int>>(x,y,z);
}
vector<func_obj> getSuitableFunc(vector<int>& states){
vector<func_obj> ret;
int cur_diff = 2e9;
for(int i=0; i<6; ++i){
for(int j=0; j<6; ++j){
if(i==j) continue;
for(int k=0; k<6; ++k){
if(k==i || k==j) continue;
vector<int> a,b,c;
for(int l=0; l<6; ++l){
if(i==l || j==l || k==l) continue;
tie(a,b,c) = getAppliedStates(states, 4, i, j, k, l);
if(maxdiff(a,b,c) <= cur_diff){
if(maxdiff(a,b,c) < cur_diff) ret.clear();
cur_diff = maxdiff(a,b,c);
ret.push_back({4, i, j, k, l});
}
}
tie(a,b,c) = getAppliedStates(states, 1, i, j, k, 0);
if(maxdiff(a,b,c) <= cur_diff){
if(maxdiff(a,b,c) < cur_diff) ret.clear();
cur_diff = maxdiff(a,b,c);
ret.push_back({1, i, j, k, 0});
}
tie(a,b,c) = getAppliedStates(states, 2, i, j, k, 0);
if(maxdiff(a,b,c) <= cur_diff){
if(maxdiff(a,b,c) < cur_diff) ret.clear();
cur_diff = maxdiff(a,b,c);
ret.push_back({2, i, j, k, 0});
}
tie(a,b,c) = getAppliedStates(states, 3, i, j, k, 0);
if(maxdiff(a,b,c) <= cur_diff){
if(maxdiff(a,b,c) < cur_diff) ret.clear();
cur_diff = maxdiff(a,b,c);
ret.push_back({3, i, j, k, 0});
}
}
}
}
return ret;
}
int pow3[] = {1, 3, 9, 27, 81, 243, 729};
func_obj lastfunc;
bool isValidState(vector<int>& states,int depth){
if(states.size() <= 1) return true;
if(depth>=6) return false;
if(states.size() > pow3[6-depth]) return false;
vector<int> a,b,c;
auto t=getSuitableFunc(states);
for(func_obj move : t){
tie(a,b,c) = getAppliedStates(states, move.type, move.a, move.b, move.c, move.d);
if(a.size()>pow3[5-depth] || b.size()>pow3[5-depth] || c.size()>pow3[5-depth]){
return false;
}
if(isValidState(a, depth+1) &&
isValidState(b, depth+1) &&
isValidState(c, depth+1)){
lastfunc = move;
return true;
}
}
return false;
}
void orderCoins() {
vector<int> states, new_states;
for(int i=0; i<720; ++i) states.push_back(i);
int depth = 0;
int first_state = -1;
while(true){
if(states.size()==1){
int s=states[0];
int ans[6];
for(int i=0;i<6;++i){
ans[lst[s][i]-1]=i+1;
}
answer(ans);
break;
}
bool isPoss;
func_obj f;
if(depth>=2){
isValidState(states, depth);
f = lastfunc;
} else if(depth==0) {
f = {1,0,1,2,0};
} else if(depth==1){
f={3, 3, 4, 5, 0};
}
auto t=getAppliedStates(states, f.type, f.a, f.b, f.c, f.d);
//scanf("%*c");
int ret;
if(f.type == 1) ret=getHeaviest(f.a+1, f.b+1, f.c+1);
if(f.type == 2) ret=getLightest(f.a+1, f.b+1, f.c+1);
if(f.type == 3) ret=getMedian(f.a+1, f.b+1, f.c+1);
if(f.type == 4) ret=getNextLightest(f.a+1, f.b+1, f.c+1, f.d+1);
if(ret == f.a+1){
states=get<0>(t);
if(depth==0) first_state = 0;
} else if(ret==f.b+1){
states=get<1>(t);
if(depth==0) first_state = 1;
} else if(ret==f.c+1){
states=get<2>(t);
if(depth==0) first_state = 2;
}
++depth;
}
}
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 'void init(int)':
scales.cpp:10:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T) {
^
scales.cpp: In function 'int maxdiff(std::vector<int>&, std::vector<int>&, std::vector<int>&)':
scales.cpp:36:18: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int a=av.size(), b=bv.size(), c=cv.size();
~~~~~~~^~
scales.cpp:36:31: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int a=av.size(), b=bv.size(), c=cv.size();
~~~~~~~^~
scales.cpp:36:44: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
int a=av.size(), b=bv.size(), c=cv.size();
~~~~~~~^~
scales.cpp: In function 'bool isValidState(std::vector<int>&, int)':
scales.cpp:114:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(states.size() > pow3[6-depth]) return false;
~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
scales.cpp:119:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a.size()>pow3[5-depth] || b.size()>pow3[5-depth] || c.size()>pow3[5-depth]){
~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:119:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a.size()>pow3[5-depth] || b.size()>pow3[5-depth] || c.size()>pow3[5-depth]){
~~~~~~~~^~~~~~~~~~~~~~
scales.cpp:119:72: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if(a.size()>pow3[5-depth] || b.size()>pow3[5-depth] || c.size()>pow3[5-depth]){
~~~~~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:147:14: warning: unused variable 'isPoss' [-Wunused-variable]
bool isPoss;
^~~~~~
scales.cpp:136:9: warning: variable 'first_state' set but not used [-Wunused-but-set-variable]
int first_state = -1;
^~~~~~~~~~~
scales.cpp:171:16: warning: 'ret' may be used uninitialized in this function [-Wmaybe-uninitialized]
} else if(ret==f.c+1){
^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
394 ms |
504 KB |
Output is correct |
| 2 |
Correct |
419 ms |
504 KB |
Output is correct |
| 3 |
Correct |
471 ms |
596 KB |
Output is correct |
| 4 |
Correct |
449 ms |
608 KB |
Output is correct |
| 5 |
Correct |
427 ms |
608 KB |
Output is correct |
| 6 |
Correct |
438 ms |
616 KB |
Output is correct |
| 7 |
Correct |
472 ms |
620 KB |
Output is correct |
| 8 |
Correct |
437 ms |
648 KB |
Output is correct |
| 9 |
Correct |
475 ms |
760 KB |
Output is correct |
| 10 |
Correct |
449 ms |
760 KB |
Output is correct |
| 11 |
Correct |
514 ms |
792 KB |
Output is correct |
| 12 |
Correct |
492 ms |
792 KB |
Output is correct |
| 13 |
Correct |
639 ms |
792 KB |
Output is correct |
| 14 |
Correct |
445 ms |
792 KB |
Output is correct |
| 15 |
Correct |
432 ms |
804 KB |
Output is correct |
| 16 |
Correct |
456 ms |
812 KB |
Output is correct |
| 17 |
Correct |
456 ms |
812 KB |
Output is correct |
| 18 |
Correct |
399 ms |
812 KB |
Output is correct |
| 19 |
Correct |
442 ms |
812 KB |
Output is correct |
| 20 |
Correct |
458 ms |
812 KB |
Output is correct |
| 21 |
Correct |
496 ms |
812 KB |
Output is correct |
| 22 |
Correct |
410 ms |
812 KB |
Output is correct |
| 23 |
Correct |
430 ms |
812 KB |
Output is correct |
| 24 |
Correct |
454 ms |
812 KB |
Output is correct |
| 25 |
Correct |
488 ms |
824 KB |
Output is correct |
| 26 |
Correct |
540 ms |
824 KB |
Output is correct |
| 27 |
Correct |
452 ms |
832 KB |
Output is correct |
| 28 |
Correct |
506 ms |
832 KB |
Output is correct |
| 29 |
Correct |
550 ms |
836 KB |
Output is correct |
| 30 |
Correct |
445 ms |
968 KB |
Output is correct |
| 31 |
Correct |
446 ms |
968 KB |
Output is correct |
| 32 |
Correct |
427 ms |
968 KB |
Output is correct |
| 33 |
Correct |
423 ms |
968 KB |
Output is correct |
| 34 |
Correct |
474 ms |
968 KB |
Output is correct |
| 35 |
Correct |
444 ms |
968 KB |
Output is correct |
| 36 |
Correct |
431 ms |
1004 KB |
Output is correct |
| 37 |
Correct |
414 ms |
1012 KB |
Output is correct |
| 38 |
Correct |
554 ms |
1012 KB |
Output is correct |
| 39 |
Correct |
542 ms |
1012 KB |
Output is correct |
| 40 |
Correct |
503 ms |
1012 KB |
Output is correct |
