제출 #870834

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
870834		abczz	저울 (IOI15_scales)	C++14	100 / 100	4 ms	5108 KiB

scales

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include "scales.h"
#define ll long long
using namespace std;

vector <array<ll, 6>> Z = {{1,0,0,1,2},{3,1,3,4,5},{9,3,1,2,3,4},{27,2,1,4,5},{81,1,0,3,4},{243,1,2,3,5},{244,1,0,2,5},{245,1,2,3,5},{82,1,1,2,3},{246,1,0,3,5},{247,1,0,3,5},{248,1,0,2,5},{83,0,1,2,3},{249,1,2,3,5},{250,1,0,1,4},{251,1,0,3,4},{28,2,2,4,5},{84,1,0,3,4},{252,1,1,3,5},{253,1,0,1,5},{254,1,1,3,5},{85,1,1,2,3},{255,1,0,3,5},{256,1,0,3,5},{257,1,0,1,5},{86,0,1,2,3},{258,1,0,1,4},{259,1,1,3,5},{260,1,0,3,4},{29,3,0,1,2,4},{87,2,1,2,3},{261,1,0,3,5},{262,1,0,3,5},{263,0,1,2,3},{88,1,0,1,5},{264,0,1,2,3},{265,0,1,2,4},{266,1,1,2,5},{89,1,0,1,5},{267,0,1,2,3},{268,0,2,4,5},{269,1,1,2,5},{10,3,1,2,3,5},{30,0,1,4,5},{90,2,1,2,3},{270,1,0,2,3},{271,1,0,1,3},{272,1,1,2,4},{91,1,1,2,4},{273,1,0,3,4},{274,1,0,3,4},{275,1,0,2,3},{92,1,0,4,5},{276,1,2,3,4},{277,1,0,2,3},{278,1,2,3,4},{31,0,2,4,5},{93,2,1,2,3},{279,1,0,2,3},{280,1,0,1,3},{281,1,1,2,4},{94,1,1,2,4},{282,1,0,3,4},{283,1,0,3,4},{284,1,0,1,3},{95,1,0,4,5},{285,1,1,3,4},{286,1,0,1,3},{287,1,1,3,4},{32,0,1,2,3},{96,1,0,4,5},{288,1,1,2,4},{289,0,2,3,4},{290,1,1,2,4},{97,1,0,4,5},{291,1,1,2,4},{292,0,1,3,4},{293,1,1,2,4},{98,3,0,1,2,3},{294,1,0,1,2},{295,1,0,4,5},{296,1,0,4,5},{11,3,1,2,3,4},{33,0,1,4,5},{99,2,1,2,3},{297,1,0,2,3},{298,1,0,1,3},{299,1,1,2,5},{100,1,0,4,5},{300,1,2,3,5},{301,1,2,3,5},{302,1,0,2,3},{101,1,1,2,5},{303,1,0,3,5},{304,1,0,3,5},{305,1,0,2,3},{34,0,2,4,5},{102,2,1,2,3},{306,1,0,2,3},{307,1,0,1,3},{308,1,1,2,5},{103,1,0,4,5},{309,1,1,3,5},{310,1,1,3,5},{311,1,0,1,3},{104,1,1,2,5},{312,1,0,3,5},{313,1,0,3,5},{314,1,0,1,3},{35,0,1,2,3},{105,1,0,4,5},{315,1,1,2,5},{316,1,1,2,5},{317,0,2,3,4},{106,1,0,4,5},{318,1,1,2,5},{319,1,1,2,5},{320,0,1,3,4},{107,3,0,1,2,3},{321,1,0,1,2},{322,1,0,4,5},{323,1,0,4,5},{4,1,3,4,5},{12,3,0,2,3,4},{36,2,0,4,5},{108,1,1,3,4},{324,1,2,3,5},{325,1,1,2,5},{326,1,2,3,5},{109,1,0,2,3},{327,1,1,3,5},{328,1,1,3,5},{329,1,1,2,5},{110,0,0,2,3},{330,1,2,3,5},{331,1,0,1,4},{332,1,1,3,4},{37,2,2,4,5},{111,1,1,3,4},{333,1,0,3,5},{334,1,0,1,5},{335,1,0,3,5},{112,1,0,2,3},{336,1,1,3,5},{337,1,1,3,5},{338,1,0,1,5},{113,0,0,2,3},{339,1,0,1,4},{340,1,0,3,5},{341,1,1,3,4},{38,3,0,1,2,4},{114,1,0,1,5},{342,0,0,2,4},{343,0,0,2,3},{344,1,0,2,5},{115,2,0,2,3},{345,1,1,3,5},{346,1,1,3,5},{347,0,0,2,3},{116,1,0,1,5},{348,0,2,4,5},{349,0,0,2,3},{350,1,0,2,5},{13,3,0,2,3,5},{39,0,0,4,5},{117,2,0,2,3},{351,1,1,2,3},{352,1,0,1,3},{353,1,0,2,4},{118,1,0,2,4},{354,1,1,3,4},{355,1,1,3,4},{356,1,1,2,3},{119,1,1,4,5},{357,1,2,3,4},{358,1,1,2,3},{359,1,2,3,4},{40,0,2,4,5},{120,2,0,2,3},{360,1,1,2,3},{361,1,0,1,3},{362,1,0,2,4},{121,1,0,2,4},{363,1,1,3,4},{364,1,1,3,4},{365,1,0,1,3},{122,1,1,4,5},{366,1,0,3,4},{367,1,0,1,3},{368,1,0,3,4},{41,0,0,2,3},{123,1,0,2,4},{369,1,1,4,5},{370,1,0,1,5},{371,1,0,1,5},{124,1,0,2,4},{372,1,0,1,5},{373,1,1,4,5},{374,1,1,2,5},{125,3,0,1,2,3},{375,1,1,4,5},{376,1,0,1,2},{377,1,1,4,5},{14,3,0,2,3,4},{42,0,0,4,5},{126,2,0,2,3},{378,1,1,2,3},{379,1,0,1,3},{380,1,0,2,5},{127,1,1,4,5},{381,1,2,3,5},{382,1,2,3,5},{383,1,1,2,3},{128,1,0,2,5},{384,1,1,3,5},{385,1,1,3,5},{386,1,1,2,3},{43,0,2,4,5},{129,2,0,2,3},{387,1,1,2,3},{388,1,0,1,3},{389,1,0,2,5},{130,1,1,4,5},{390,1,0,3,5},{391,1,0,3,5},{392,1,0,1,3},{131,1,0,2,5},{393,1,1,3,5},{394,1,1,3,5},{395,1,0,1,3},{44,0,0,2,3},{132,1,0,2,5},{396,1,1,4,5},{397,1,0,1,4},{398,1,0,1,4},{133,1,0,2,5},{399,1,0,1,4},{400,1,1,4,5},{401,1,1,2,4},{134,3,0,1,2,3},{402,1,1,4,5},{403,1,0,1,2},{404,1,1,4,5},{5,1,3,4,5},{15,3,0,1,3,4},{45,2,0,4,5},{135,1,2,3,4},{405,1,1,3,5},{406,1,1,2,5},{407,1,1,3,5},{136,1,0,1,3},{408,1,2,3,5},{409,1,2,3,5},{410,1,1,2,5},{137,0,0,1,3},{411,1,1,3,5},{412,1,0,2,4},{413,1,2,3,4},{46,2,1,4,5},{138,1,2,3,4},{414,1,0,3,5},{415,1,0,2,5},{416,1,0,3,5},{139,1,0,1,3},{417,1,2,3,5},{418,1,2,3,5},{419,1,0,2,5},{140,0,0,1,3},{420,1,0,2,4},{421,1,0,3,5},{422,1,2,3,4},{47,3,0,1,2,4},{141,1,0,2,5},{423,0,0,1,4},{424,0,0,1,3},{425,1,0,1,5},{142,1,0,2,5},{426,0,1,4,5},{427,0,0,1,3},{428,1,0,1,5},{143,2,0,1,3},{429,1,2,3,5},{430,1,2,3,5},{431,0,0,1,3},{16,3,0,1,3,5},{48,0,0,4,5},{144,2,0,1,3},{432,1,1,2,3},{433,1,0,2,3},{434,1,0,1,4},{145,1,0,1,4},{435,1,2,3,4},{436,1,2,3,4},{437,1,1,2,3},{146,1,2,4,5},{438,1,1,3,4},{439,1,1,2,3},{440,1,1,3,4},{49,0,1,4,5},{147,2,0,1,3},{441,1,1,2,3},{442,1,0,2,3},{443,1,0,1,4},{148,1,0,1,4},{444,1,2,3,4},{445,1,2,3,4},{446,1,0,2,3},{149,1,2,4,5},{447,1,0,3,4},{448,1,0,2,3},{449,1,0,3,4},{50,0,0,1,3},{150,1,0,1,4},{450,1,2,4,5},{451,1,0,2,5},{452,1,0,2,5},{151,1,0,1,4},{453,1,0,2,5},{454,1,2,4,5},{455,1,1,2,5},{152,3,0,1,2,3},{456,1,2,4,5},{457,1,2,4,5},{458,1,0,1,2},{17,3,0,1,3,4},{51,0,0,4,5},{153,2,0,1,3},{459,1,1,2,3},{460,1,0,2,3},{461,1,0,1,5},{154,1,2,4,5},{462,1,1,3,5},{463,1,1,3,5},{464,1,1,2,3},{155,1,0,1,5},{465,1,2,3,5},{466,1,2,3,5},{467,1,1,2,3},{52,0,1,4,5},{156,2,0,1,3},{468,1,1,2,3},{469,1,0,2,3},{470,1,0,1,5},{157,1,2,4,5},{471,1,0,3,5},{472,1,0,3,5},{473,1,0,2,3},{158,1,0,1,5},{474,1,2,3,5},{475,1,2,3,5},{476,1,0,2,3},{53,0,0,1,3},{159,1,0,1,5},{477,1,2,4,5},{478,1,0,2,4},{479,1,0,2,4},{160,1,0,1,5},{480,1,0,2,4},{481,1,2,4,5},{482,1,1,2,4},{161,3,0,1,2,3},{483,1,2,4,5},{484,1,2,4,5},{485,1,0,1,2}};

array<ll, 4> A[100000];
vector <array<ll, 6>> Q[100000];
ll ty[100000];

void init(int T) {
  for (auto u : Z) {
    ty[u[0]] = u[1];
    if (u[1] == 3) A[u[0]] = {u[2]+1, u[3]+1, u[4]+1, u[5]+1};
    else A[u[0]] = {u[2]+1, u[3]+1, u[4]+1};
  }
  return;
}

ll get(ll v, ll id) {
  if (A[id][0] == v) return 0;
  else if (A[id][1] == v) return 1;
  else return 2;
}

void solve(ll u, ll id) {
  if (u == 6) {
    int R[6];
    for (int i=0; i<6; ++i) R[Q[id][0][i]-1] = i+1;
    answer(R);
    return;
  }
  ll ret, f, a, b, c;
  a = A[id][0]-1, b = A[id][1]-1, c = A[id][2]-1;
  for (auto x : Q[id]) {
    if (!ty[id]) {
      if (x[a] > x[b] && x[a] > x[c]) Q[id*3].push_back(x);
      else if (x[a] < x[b] && x[b] > x[c]) Q[id*3+1].push_back(x);
      else Q[id*3+2].push_back(x);
    }
    else if (ty[id] == 1) {
      if ((x[a] > x[b]) ^ (x[a] > x[c])) Q[id*3].push_back(x);
      else if ((x[a] < x[b]) ^ (x[b] > x[c])) Q[id*3+1].push_back(x);
      else Q[id*3+2].push_back(x);
    }
    else if (ty[id] == 2) {
      if (x[a] < x[b] && x[a] < x[c]) Q[id*3].push_back(x);
      else if (x[a] > x[b] && x[b] < x[c]) Q[id*3+1].push_back(x);
      else Q[id*3+2].push_back(x);
    }
    else {
      ll cur = 1e18, cid = -1, d = A[id][3]-1;
      if (x[d] < x[a] && x[a] < cur) cur = x[a], cid = id*3;
      if (x[d] < x[b] && x[b] < cur) cur = x[b], cid = id*3+1;
      if (x[d] < x[c] && x[c] < cur) cur = x[c], cid = id*3+2;
      if (cid == -1) {
        if (x[a] < x[b] && x[a] < x[c]) cid = id*3;
        else if (x[b] < x[a] && x[b] < x[c]) cid = id*3+1;
        else cid = id*3+2;
      }
      Q[cid].push_back(x);
    }
  }
  if (!ty[id]) ret = getHeaviest(A[id][0], A[id][1], A[id][2]);
  else if (ty[id] == 1) ret = getMedian(A[id][0], A[id][1], A[id][2]);
  else if (ty[id] == 2) ret = getLightest(A[id][0], A[id][1], A[id][2]);
  else ret = getNextLightest(A[id][0], A[id][1], A[id][2], A[id][3]);
  f = get(ret, id);
  solve(u+1, id*3+f);
}
void orderCoins() {
  for (int i=0; i<100000; ++i) Q[i].clear();
  array <ll, 6> F = {1, 2, 3, 4, 5, 6};
  Q[1].push_back(F);
  while(next_permutation(F.begin(), F.end())) {
    Q[1].push_back(F);
  }
  solve(0, 1);
}

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'void init(int)':
scales.cpp:15:15: warning: unused parameter 'T' [-Wunused-parameter]
   15 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void solve(long long int, long long int)':
scales.cpp:68:62: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   68 |   if (!ty[id]) ret = getHeaviest(A[id][0], A[id][1], A[id][2]);
      |                                                              ^
scales.cpp:68:62: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:68:62: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:69:69: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   69 |   else if (ty[id] == 1) ret = getMedian(A[id][0], A[id][1], A[id][2]);
      |                                                                     ^
scales.cpp:69:69: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:69:69: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:70:71: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   70 |   else if (ty[id] == 2) ret = getLightest(A[id][0], A[id][1], A[id][2]);
      |                                                                       ^
scales.cpp:70:71: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:70:71: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:71:68: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
   71 |   else ret = getNextLightest(A[id][0], A[id][1], A[id][2], A[id][3]);
      |                                                                    ^
scales.cpp:71:68: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:71:68: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]
scales.cpp:71:68: warning: conversion from 'std::array<long long int, 4>::value_type' {aka 'long long int'} to 'int' may change value [-Wconversion]

• Subtask 1: 100 / 100