| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 824089 |
2023-08-13T13:41:39 Z |
Khizri |
Scales (IOI15_scales) |
C++17 |
|
16 ms |
5448 KB |
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
const int mxn=2e5+5;
vector<vector<int>>vt[mxn];
int L[mxn],R[mxn],M[mxn],iq[mxn],jq[mxn],kq[mxn],dq[mxn],op[mxn],nxt=1;
int fnd(int i,int j,int k,int a,vector<int>&vt){
if(max(vt[i],max(vt[j],vt[k]))<vt[a]){
int mn=min(vt[i],min(vt[j],vt[k]));
if(mn==vt[i]) return i;
if(mn==vt[j]) return j;
return k;
}
vector<int>v={vt[i],vt[j],vt[k]};
sort(all(v));
int mn;
if(v[0]>vt[a]){
mn=v[0];
}
else if(v[1]>vt[a]){
mn=v[1];
}
else{
mn=v[2];
}
if(mn==vt[i]) return i;
if(mn==vt[j]) return j;
return k;
}
void build(int node){
ll mx=INF;
int ix,jx,kx,dx=0;
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
for(int k=j+1;k<6;k++){
ll a=0,b=0,c=0;
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][i]>max(vt[node][idx][j],vt[node][idx][k])){
a++;
}
else if(vt[node][idx][j]>max(vt[node][idx][i],vt[node][idx][k])){
b++;
}
else{
c++;
}
}
if(max({a,b,c})<mx){
mx=max({a,b,c});
op[node]=1;
ix=i,jx=j,kx=k;
}
}
}
}
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
for(int k=j+1;k<6;k++){
ll a=0,b=0,c=0;
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][i]<min(vt[node][idx][j],vt[node][idx][k])){
a++;
}
else if(vt[node][idx][j]<min(vt[node][idx][i],vt[node][idx][k])){
b++;
}
else{
c++;
}
}
if(max({a,b,c})<mx){
mx=max({a,b,c});
op[node]=2;
ix=i,jx=j,kx=k;
}
}
}
}
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
for(int k=j+1;k<6;k++){
ll a=0,b=0,c=0;
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][i]>min(vt[node][idx][j],vt[node][idx][k])&&vt[node][idx][i]<max(vt[node][idx][j],vt[node][idx][k])){
a++;
}
else if(vt[node][idx][j]>min(vt[node][idx][i],vt[node][idx][k])&&vt[node][idx][j]<max(vt[node][idx][i],vt[node][idx][k])){
b++;
}
else{
c++;
}
}
if(max({a,b,c})<mx){
mx=max({a,b,c});
op[node]=3;
ix=i,jx=j,kx=k;
}
}
}
}
for(int d=0;d<6;d++){
for(int i=0;i<6;i++){
if(i==d) continue;
for(int j=i+1;j<6;j++){
if(j==d) continue;
for(int k=j+1;k<6;k++){
if(k==d) continue;
ll a=0,b=0,c=0;
for(int idx=0;idx<vt[node].size();idx++){
int res=fnd(i,j,k,d,vt[node][idx]);
if(res==i){
a++;
}
else if(res==j){
b++;
}
else{
c++;
}
}
if(max({a,b,c})<mx){
mx=max({a,b,c});
op[node]=4;
ix=i,jx=j,kx=k,dx=d;
}
}
}
}
}
L[node]=++nxt;
M[node]=++nxt;
R[node]=++nxt;
iq[node]=ix;
jq[node]=jx;
kq[node]=kx;
dq[node]=dx;
//cout<<L[node]<<' '<<M[node]<<' '<<R[node]<<endl;
if(op[node]==1){
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
vt[L[node]].pb(vt[node][idx]);
}
else if(vt[node][idx][jx]>max(vt[node][idx][ix],vt[node][idx][kx])){
vt[M[node]].pb(vt[node][idx]);
}
else{
vt[R[node]].pb(vt[node][idx]);
}
}
}
else if(op[node]==2){
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][ix]<min(vt[node][idx][jx],vt[node][idx][kx])){
vt[L[node]].pb(vt[node][idx]);
}
else if(vt[node][idx][jx]<min(vt[node][idx][ix],vt[node][idx][kx])){
vt[M[node]].pb(vt[node][idx]);
}
else{
vt[R[node]].pb(vt[node][idx]);
}
}
}
else if(op[node]==3){
for(int idx=0;idx<vt[node].size();idx++){
if(vt[node][idx][ix]>min(vt[node][idx][jx],vt[node][idx][kx])&&vt[node][idx][ix]<max(vt[node][idx][jx],vt[node][idx][kx])){
vt[L[node]].pb(vt[node][idx]);
}
else if(vt[node][idx][jx]>min(vt[node][idx][ix],vt[node][idx][kx])&&vt[node][idx][jx]<max(vt[node][idx][ix],vt[node][idx][kx])){
vt[M[node]].pb(vt[node][idx]);
}
else{
vt[R[node]].pb(vt[node][idx]);
}
}
}
else{
for(int idx=0;idx<vt[node].size();idx++){
int res=fnd(ix,jx,kx,dx,vt[node][idx]);
if(res==ix){
vt[L[node]].pb(vt[node][idx]);
}
else if(res==jx){
vt[M[node]].pb(vt[node][idx]);
}
else{
vt[R[node]].pb(vt[node][idx]);
}
}
}
if(vt[L[node]].size()>1){
build(L[node]);
}
if(vt[M[node]].size()>1){
build(M[node]);
}
if(vt[R[node]].size()>1){
build(R[node]);
}
}
vector<int>query(int node){
if(vt[node].size()==1){
return vt[node][0];
}
//cout<<vt[node].size()<<endl;
int x;
if(op[node]==1){
//cout<<1<<' '<<iq[node]+1<<' '<<jq[node]+1<<' '<<kq[node]+1<<endl;
x=getHeaviest(iq[node]+1,jq[node]+1,kq[node]+1);
}
else if(op[node]==2){
//cout<<0<<' '<<iq[node]+1<<' '<<jq[node]+1<<' '<<kq[node]+1<<endl;
x=getLightest(iq[node]+1,jq[node]+1,kq[node]+1);
}
else if(op[node]==3){
x=getMedian(iq[node]+1,jq[node]+1,kq[node]+1);
}
else{
x=getNextLightest(iq[node]+1,jq[node]+1,kq[node]+1,dq[node]+1);
}
if(x==iq[node]+1){
return query(L[node]);
}
else if(x==jq[node]+1){
return query(M[node]);
}
else{
return query(R[node]);
}
}
void init(int T) {
vector<int>v(6);
iota(all(v),1);
do{
vt[1].pb(v);
}while(next_permutation(all(v)));
build(1);
}
void orderCoins() {
vector<int>vt=query(1);
int arr[6];
for(int i=0;i<6;i++){
arr[vt[i]-1]=i+1;
}
answer(arr);
}
/*
g++ scales.cpp grader.cpp ; .\a.exe
*/
Compilation message
scales.cpp: In function 'int fnd(int, int, int, int, std::vector<int>&)':
scales.cpp:19:45: warning: declaration of 'vt' shadows a global declaration [-Wshadow]
19 | int fnd(int i,int j,int k,int a,vector<int>&vt){
| ~~~~~~~~~~~~^~
scales.cpp:17:20: note: shadowed declaration is here
17 | vector<vector<int>>vt[mxn];
| ^~
scales.cpp: In function 'void build(int)':
scales.cpp:49:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:72:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:95:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
95 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:122:38: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
122 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:152:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:165:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
165 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:178:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
178 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp:191:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
191 | for(int idx=0;idx<vt[node].size();idx++){
| ~~~^~~~~~~~~~~~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:244:15: warning: unused parameter 'T' [-Wunused-parameter]
244 | void init(int T) {
| ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:254:16: warning: declaration of 'vt' shadows a global declaration [-Wshadow]
254 | vector<int>vt=query(1);
| ^~
scales.cpp:17:20: note: shadowed declaration is here
17 | vector<vector<int>>vt[mxn];
| ^~
scales.cpp: In function 'void build(int)':
scales.cpp:153:72: warning: 'kx' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
| ^
scales.cpp:153:54: warning: 'jx' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
| ^
scales.cpp:153:32: warning: 'ix' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | if(vt[node][idx][ix]>max(vt[node][idx][jx],vt[node][idx][kx])){
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
13 ms |
5348 KB |
Output is partially correct |
| 2 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 3 |
Partially correct |
13 ms |
5384 KB |
Output is partially correct |
| 4 |
Partially correct |
13 ms |
5332 KB |
Output is partially correct |
| 5 |
Partially correct |
13 ms |
5332 KB |
Output is partially correct |
| 6 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 7 |
Partially correct |
12 ms |
5324 KB |
Output is partially correct |
| 8 |
Partially correct |
12 ms |
5320 KB |
Output is partially correct |
| 9 |
Partially correct |
15 ms |
5316 KB |
Output is partially correct |
| 10 |
Partially correct |
13 ms |
5368 KB |
Output is partially correct |
| 11 |
Partially correct |
13 ms |
5312 KB |
Output is partially correct |
| 12 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 13 |
Partially correct |
12 ms |
5412 KB |
Output is partially correct |
| 14 |
Partially correct |
15 ms |
5316 KB |
Output is partially correct |
| 15 |
Partially correct |
12 ms |
5352 KB |
Output is partially correct |
| 16 |
Partially correct |
16 ms |
5448 KB |
Output is partially correct |
| 17 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 18 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 19 |
Partially correct |
13 ms |
5388 KB |
Output is partially correct |
| 20 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 21 |
Partially correct |
13 ms |
5348 KB |
Output is partially correct |
| 22 |
Partially correct |
12 ms |
5376 KB |
Output is partially correct |
| 23 |
Partially correct |
12 ms |
5396 KB |
Output is partially correct |
| 24 |
Partially correct |
12 ms |
5424 KB |
Output is partially correct |
| 25 |
Partially correct |
12 ms |
5436 KB |
Output is partially correct |
| 26 |
Partially correct |
12 ms |
5316 KB |
Output is partially correct |
| 27 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 28 |
Partially correct |
13 ms |
5380 KB |
Output is partially correct |
| 29 |
Partially correct |
13 ms |
5352 KB |
Output is partially correct |
| 30 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 31 |
Partially correct |
12 ms |
5320 KB |
Output is partially correct |
| 32 |
Partially correct |
15 ms |
5332 KB |
Output is partially correct |
| 33 |
Partially correct |
12 ms |
5304 KB |
Output is partially correct |
| 34 |
Partially correct |
12 ms |
5320 KB |
Output is partially correct |
| 35 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 36 |
Partially correct |
12 ms |
5332 KB |
Output is partially correct |
| 37 |
Partially correct |
14 ms |
5316 KB |
Output is partially correct |
| 38 |
Partially correct |
13 ms |
5316 KB |
Output is partially correct |
| 39 |
Partially correct |
13 ms |
5308 KB |
Output is partially correct |
| 40 |
Partially correct |
12 ms |
5324 KB |
Output is partially correct |
