Submission #287691

#	Time	Username	Problem	Language	Result	Execution time	Memory
287691		shayan_p	Scales (IOI15_scales)	C++17	100 / 100	98 ms	10104 KiB

scales

// Oh damn! Suddenly you're free to fly...

#include<bits/stdc++.h>
#include "scales.h"

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 1e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int perms[720][6];
int arr[6];

struct node{
    vector<int> posib;
    int A, B, C, D, Task;
    node *v[3];
};
node* root;

int fnd(int id, int x){
    assert(id < 720);
    for(int i = 0; i < 6; i++)
	if(perms[id][i] == x)
	    return i;
    assert(0);
}
function<int(int,int,int,int,int)> calc[4] = {
					     [](int id, int a, int b, int c, int d = -1){
						 a = fnd(id, a), b = fnd(id, b), c = fnd(id, c);
						 int mx = max({a, b, c});
						 if(mx == a)
						     return 0;
						 if(mx == b)
						     return 1;
						 if(mx == c)
						     return 2;
						 assert(0);
					     },
					     [](int id, int a, int b, int c, int d  = -1){
						 a = fnd(id, a), b = fnd(id, b), c = fnd(id, c);
						 int A = a, B = b, C = c;
						 if(A > B)
						     swap(A, B);
						 if(A > C)
						     swap(A, C);
						 if(B > C)
						     swap(B, C);
						 if(B == a)
						     return 0;
						 if(B == b)
						     return 1;
						 if(B == c)
						     return 2;
						 assert(0);
					     },
					     [](int id, int a, int b, int c, int d = -1){
						 a = fnd(id, a), b = fnd(id, b), c = fnd(id, c);
						 int mn = min({a, b, c});
						 if(mn == a)
						     return 0;
						 if(mn == b)
						     return 1;
						 if(mn == c)
						     return 2;
						 assert(0);
					     },
					     [](int id, int a, int b, int c, int d){
						 a = fnd(id, a), b = fnd(id, b), c = fnd(id, c), d = fnd(id, d);
						 int A = a, B = b, C = c;
						 if(A > B)
						     swap(A, B);
						 if(A > C)
						     swap(A, C);
						 if(B > C)
						     swap(B, C);
						 int ret = -1;
						 if(d < A)
						     ret = A;
						 else if(d < B)
						     ret = B;
						 else if(d < C)
						     ret = C;
						 else
						     ret = A;
						 if(a == ret)
						     return 0;
						 if(b == ret)
						     return 1;
						 if(c == ret)
						     return 2;
						 assert(0);
					     }
};
int mx_task(int task, vector<int> &v, int a, int b, int c, int d = -1){
    int sc[3] = {0, 0, 0};
    for(int id : v)
	sc[calc[task](id, a, b, c, d)]++;
    return max({sc[0], sc[1], sc[2]});
}
int dif_task(int task, vector<int> &v, int a, int b, int c, int d = -1){
    int sc[3] = {0, 0, 0};
    for(int id : v)
	sc[calc[task](id, a, b, c, d)]++;
    return max({sc[0], sc[1], sc[2]}) - min({sc[0], sc[1], sc[2]});
}
void fil_task(int task, node *u, int a, int b, int c, int d = -1){
    u->A = a, u->B = b, u->C = c, u->D = d, u->Task = task;
    u->v[0] = new node(), u->v[1] = new node(), u->v[2] = new node();
    for(int id : u->posib)
	u->v[calc[task](id, a, b, c, d)]->posib.PB(id);
}

int TW[10];

bool dfs(node* u, int h = 0){
    assert(h <= 6);
    if(h == 6)
	assert(sz(u->posib) <= 1);
    if(sz(u->posib) <= 1)
	return 1;
    for(int i = 0; i < 6; i++)
	for(int j = i+1; j < 6; j++)
	    for(int k = j+1; k < 6; k++){
		fil_task(0, u, i, j, k);
		if(mx_task(0, u->posib, i, j, k) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
		    return 1;
		fil_task(1, u, i, j, k);
		if(mx_task(1, u->posib, i, j, k) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
		    return 1;
		fil_task(2, u, i, j, k);
		if(mx_task(2, u->posib, i, j, k) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
		    return 1;
		for(int w = 0; w < 6; w++){
		    if(w != i && w != j && w != k){
			fil_task(3, u, i, j, k, w);
			if(mx_task(3, u->posib, i, j, k, w) <= TW[6-h-1] && dfs(u->v[0], h+1) && dfs(u->v[1], h+1) && dfs(u->v[2], h+1))
			    return 1;			
		    }			
		}
	    }
    return 0;
    /*    int bst = inf, cntbst = 0;
    auto better = [&](int x){
		      if(x < bst)
			  bst = x, cntbst = 0;
		      cntbst+= x == bst;
		  };
    for(int i = 0; i < 6; i++)
	for(int j = i+1; j < 6; j++)
	    for(int k = j+1; k < 6; k++){
		better(dif_task(0, u->posib, i, j, k));
		better(dif_task(1, u->posib, i, j, k));
		better(dif_task(2, u->posib, i, j, k));
		for(int w = 0; w < 6; w++){
		    if(w != i && w != j && w != k){
			better(dif_task(3, u->posib, i, j, k, w));
		    }			
		}
	    }
    cntbst = rand() % cntbst;
    for(int i = 0; i < 6; i++)
	for(int j = i+1; j < 6; j++)
	    for(int k = j+1; k < 6; k++){
		if(bst == dif_task(0, u->posib, i, j, k) && cntbst-- == 0){
		    fil_task(0, u, i, j, k);
		    goto Hell;
		}
		if(bst == dif_task(1, u->posib, i, j, k) && cntbst-- == 0){
		    fil_task(1, u, i, j, k);
		    goto Hell;
		}
		if(bst == dif_task(2, u->posib, i, j, k) && cntbst-- == 0){
		    fil_task(2, u, i, j, k);
		    goto Hell;
		}
		for(int w = 0; w < 6; w++){
		    if(w != i && w != j && w != k){
			if(bst == dif_task(3, u->posib, i, j, k, w) && cntbst-- == 0){
			    fil_task(3, u, i, j, k, w);
			    goto Hell;
			}
		    }			
		}
	    }
 Hell:;
    cerr << sz(u->posib) << ": " << sz(u->v[0]->posib) << " " << sz(u->v[1]->posib) << " " << sz(u->v[2]->posib) << endl;
    dfs(u->v[0], h+1), dfs(u->v[1], h+1), dfs(u->v[2], h+1);
    return;*/
    
}
void init(int T){
    TW[0] = 1;
    for(int i = 1; i < 10; i++)
	TW[i] = 3 * TW[i-1];
    
    srand(time(0));
    
    iota(arr, arr + 6, 0);
    int C = 0;
    do{
	for(int i = 0; i < 6; i++)
	    perms[C][i] = arr[i];
	C++;
    }while(next_permutation(arr, arr + 6));
    root = new node();
    for(int i = 0; i < 720; i++){
	root->posib.PB(i);
    }
    dfs(root);
}

void orderCoins(){
    node *now = root;
    int asked = 0;
    while(sz(now->posib) > 1){
	int id = -1;
	if(now->Task == 0)
	    id = getHeaviest(now->A + 1, now->B + 1, now->C + 1);
	else if(now->Task == 1)
	    id = getMedian(now->A + 1, now->B + 1, now->C + 1);
	else if(now->Task == 2)
	    id = getLightest(now->A + 1, now->B + 1, now->C + 1);
	else if(now->Task == 3)
	    id = getNextLightest(now->A + 1, now->B + 1, now->C + 1, now->D + 1);
	if(id == now->A + 1)
	    id = 0;
	else if(id == now->B + 1)
	    id = 1;
	else
	    id = 2;
	now = now->v[id];
	asked++;
    }
    int ans[6];
    for(int i = 0; i < 6; i++){
	ans[i] = perms[now->posib[0]][i] + 1;
    }
    answer(ans);
    // answer
    // getHeaviest
    // getMedian
    // getLightest
    // getNextLightest
}

Compilation message (stderr)

scales.cpp: In lambda function:
scales.cpp:37:47: warning: unused parameter 'd' [-Wunused-parameter]
   37 |           [](int id, int a, int b, int c, int d = -1){
      |                                           ~~~~^~~~~~
scales.cpp: In lambda function:
scales.cpp:48:47: warning: unused parameter 'd' [-Wunused-parameter]
   48 |           [](int id, int a, int b, int c, int d  = -1){
      |                                           ~~~~^~~~~~~
scales.cpp: In lambda function:
scales.cpp:65:47: warning: unused parameter 'd' [-Wunused-parameter]
   65 |           [](int id, int a, int b, int c, int d = -1){
      |                                           ~~~~^~~~~~
scales.cpp: In function 'void init(int)':
scales.cpp:205:15: warning: conversion from 'time_t' {aka 'long int'} to 'unsigned int' may change value [-Wconversion]
  205 |     srand(time(0));
      |           ~~~~^~~
scales.cpp:200:15: warning: unused parameter 'T' [-Wunused-parameter]
  200 | void init(int T){
      |           ~~~~^

• Subtask 1: 100 / 100