oj.uz

Submission #940792

# Submission time Handle Problem Language Result Execution time Memory
940792 2024-03-07T15:57:57 Z AdamGS Scales (IOI15_scales) C++17
71.4286 / 100
 395 ms 2956 KB 
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int INF=1e9+7;
struct node {
  int typ=-1, A, B, C, D;
  int nxta, nxtb, nxtc;
  vector<int>P;
};
node puste;
vector<node>V;
int solve(vector<vector<int>>&T, int ind, int dep);
int get_hev(vector<int>&T, int A, int B, int C) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  return P[2].nd;
}
int get_lig(vector<int>&T, int A, int B, int C) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  return P[0].nd;
}
int get_med(vector<int>&T, int A, int B, int C) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  return P[1].nd;
}
int get_nxt(vector<int>&T, int A, int B, int C, int D) {
  vector<pair<int,int>>P;
  P.pb({T[A], A});
  P.pb({T[B], B});
  P.pb({T[C], C});
  sort(all(P));
  for(auto i : P) if(i.st>T[D]) return i.nd;
  return P[0].nd;
}
int rob(vector<vector<int>>&T, int ind, int dep, int typ, int A, int B, int C, int D) {
  vector<vector<int>>X, Y, Z;
  for(auto i : T) {
    int p;
    if(typ==0) p=get_hev(i, A, B, C);
    if(typ==1) p=get_lig(i, A, B, C);
    if(typ==2) p=get_med(i, A, B, C);
    if(typ==3) p=get_nxt(i, A, B, C, D);
    if(p==A) X.pb(i);
    if(p==B) Y.pb(i);
    if(p==C) Z.pb(i);
  }
  V[ind].typ=typ;
  V[ind].A=A;
  V[ind].B=B;
  V[ind].C=C;
  V[ind].D=D;
  int ans=0;
  if(X.size()) {
    V[ind].nxta=V.size();
    V.pb(puste);
    ans=max(ans, solve(X, V[ind].nxta, dep+1)+1);
  }
  if(Y.size()) {
    V[ind].nxtb=V.size();
    V.pb(puste);
    ans=max(ans, solve(Y, V[ind].nxtb, dep+1)+1);
  }
  if(Z.size()) {
    V[ind].nxtc=V.size();
    V.pb(puste);
    ans=max(ans, solve(Z, V[ind].nxtc, dep+1)+1);
  }
  return ans;
}
int solve(vector<vector<int>>&T, int ind, int dep) {
  if(T.size()==1) V[ind].P=T[0];
  if(T.size()<=1) return 0;
  int mi=INF;
  rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
    int x=0, y=0, z=0;
    for(auto i : T) {
      int p=get_hev(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    mi=min(mi, max(max(x, y), z));
    x=y=z=0;
    for(auto i : T) {
      int p=get_lig(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    mi=min(mi, max(max(x, y), z));
    x=y=z=0;
    for(auto i : T) {
      int p=get_med(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    mi=min(mi, max(max(x, y), z));
    rep(D, 6) if(A!=D && B!=D && C!=D) {
      x=y=z=0;
      for(auto i : T) {
        int p=get_nxt(i, A, B, C, D);
        if(p==A) ++x;
        if(p==B) ++y;
        if(p==C) ++z;
      }
      mi=min(mi, max(max(x, y), z));
    }
  }
  rep(A, 6) rep(B, 6) rep(C, 6) if(A!=B && A!=C && B!=C) {
    int x=0, y=0, z=0;
    for(auto i : T) {
      int p=get_hev(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    if(max(max(x, y), z)==mi) {
      int q=rob(T, ind, dep, 0, A, B, C, 0);
      if(q+dep<=6) return q;
    }
    x=y=z=0;
    for(auto i : T) {
      int p=get_lig(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    if(max(max(x, y), z)==mi) {
      int q=rob(T, ind, dep, 1, A, B, C, 0);
      if(q+dep<=6) return q;
    }
    x=y=z=0;
    for(auto i : T) {
      int p=get_med(i, A, B, C);
      if(p==A) ++x;
      if(p==B) ++y;
      if(p==C) ++z;
    }
    if(max(max(x, y), z)==mi) {
      int q=rob(T, ind, dep, 2, A, B, C, 0);
      if(q+dep<=6) return q;
    }
    rep(D, 6) if(A!=D && B!=D && C!=D) {
      x=y=z=0;
      for(auto i : T) {
        int p=get_nxt(i, A, B, C, D);
        if(p==A) ++x;
        if(p==B) ++y;
        if(p==C) ++z;
      }
      if(max(max(x, y), z)==mi) {
        int q=rob(T, ind, dep, 3, A, B, C, D);
        if(q+dep<=6) return q;
      }
    }
  }
  return 0;
}
void init(int T) {
  V.pb(puste);
  vector<vector<int>>P;
  vector<int>X;
  rep(i, 6) X.pb(i);
  do P.pb(X); while(next_permutation(all(X)));
  solve(P, 0, 0);
}
void zejdz(int x) {
  if(V[x].P.size()==6) {
    int ans[6];
    rep(i, 6) ans[V[x].P[i]]=i+1;
    answer(ans);
    return;
  }
  int p;
  if(V[x].typ==0) p=getHeaviest(V[x].A+1, V[x].B+1, V[x].C+1);
  if(V[x].typ==1) p=getLightest(V[x].A+1, V[x].B+1, V[x].C+1);
  if(V[x].typ==2) p=getMedian(V[x].A+1, V[x].B+1, V[x].C+1);
  if(V[x].typ==3) p=getNextLightest(V[x].A+1, V[x].B+1, V[x].C+1, V[x].D+1);
  if(p==V[x].A+1) zejdz(V[x].nxta);
  if(p==V[x].B+1) zejdz(V[x].nxtb);
  if(p==V[x].C+1) zejdz(V[x].nxtc);
}
void orderCoins() {
  zejdz(0);
}

Compilation message

scales.cpp: In function 'int rob(std::vector<std::vector<int> >&, int, int, int, int, int, int, int)':
scales.cpp:70:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   70 |     V[ind].nxta=V.size();
      |                 ~~~~~~^~
scales.cpp:75:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   75 |     V[ind].nxtb=V.size();
      |                 ~~~~~~^~
scales.cpp:80:23: warning: conversion from 'std::vector<node>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   80 |     V[ind].nxtc=V.size();
      |                 ~~~~~~^~
scales.cpp: In function 'void init(int)':
scales.cpp:176:15: warning: unused parameter 'T' [-Wunused-parameter]
  176 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void zejdz(int)':
scales.cpp:196:3: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
  196 |   if(p==V[x].A+1) zejdz(V[x].nxta);
      |   ^~
scales.cpp: In function 'int rob(std::vector<std::vector<int> >&, int, int, int, int, int, int, int)':
scales.cpp:61:5: warning: 'p' may be used uninitialized in this function [-Wmaybe-uninitialized]
   61 |     if(p==C) Z.pb(i);
      |     ^~

Subtask #1
71.428571 / 100.0

# Verdict Execution time Memory Grader output
1 Partially correct 378 ms 2816 KB Output is partially correct
2 Partially correct 350 ms 2692 KB Output is partially correct
3 Partially correct 359 ms 2824 KB Output is partially correct
4 Partially correct 347 ms 2696 KB Output is partially correct
5 Partially correct 392 ms 2676 KB Output is partially correct
6 Partially correct 353 ms 2736 KB Output is partially correct
7 Partially correct 351 ms 2668 KB Output is partially correct
8 Partially correct 355 ms 2756 KB Output is partially correct
9 Partially correct 350 ms 2692 KB Output is partially correct
10 Partially correct 348 ms 2700 KB Output is partially correct
11 Partially correct 348 ms 2664 KB Output is partially correct
12 Partially correct 351 ms 2700 KB Output is partially correct
13 Partially correct 352 ms 2820 KB Output is partially correct
14 Partially correct 353 ms 2700 KB Output is partially correct
15 Partially correct 354 ms 2956 KB Output is partially correct
16 Partially correct 349 ms 2780 KB Output is partially correct
17 Partially correct 352 ms 2700 KB Output is partially correct
18 Partially correct 350 ms 2832 KB Output is partially correct
19 Partially correct 388 ms 2716 KB Output is partially correct
20 Partially correct 349 ms 2696 KB Output is partially correct
21 Partially correct 358 ms 2652 KB Output is partially correct
22 Partially correct 347 ms 2668 KB Output is partially correct
23 Partially correct 387 ms 2860 KB Output is partially correct
24 Partially correct 357 ms 2832 KB Output is partially correct
25 Partially correct 388 ms 2832 KB Output is partially correct
26 Partially correct 348 ms 2700 KB Output is partially correct
27 Partially correct 348 ms 2676 KB Output is partially correct
28 Partially correct 353 ms 2696 KB Output is partially correct
29 Partially correct 350 ms 2672 KB Output is partially correct
30 Partially correct 349 ms 2680 KB Output is partially correct
31 Partially correct 354 ms 2816 KB Output is partially correct
32 Partially correct 383 ms 2696 KB Output is partially correct
33 Partially correct 352 ms 2836 KB Output is partially correct
34 Partially correct 358 ms 2692 KB Output is partially correct
35 Partially correct 375 ms 2696 KB Output is partially correct
36 Partially correct 376 ms 2768 KB Output is partially correct
37 Partially correct 395 ms 2668 KB Output is partially correct
38 Partially correct 356 ms 2808 KB Output is partially correct
39 Partially correct 350 ms 2716 KB Output is partially correct
40 Partially correct 363 ms 2768 KB Output is partially correct