Submission #1029279

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029279		pcc	Scales (IOI15_scales)	C++17	100 / 100	31 ms	51328 KiB

scales

#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")

string inp = R"(
364
14 102 64 63 107 52 38 38 107 116 29 17 107 38 29 17 43 27 116 52 17 92 9 9 38 111 17 94 112 31 27 22 110 17 92 3 3 87 62 87 17 17 111 0 55 116 45 17 107 118 22 17 3 17 17 116 18 31 98 116 94 2 98 16 16 22 94 94 98 108 63 38 112 118 87 38 112 62 107 3 29 3 87 89 107 38 38 29 105 94 116 94 105 38 119 94 43 41 112 21 17 118 116 52 9 111 17 112 94 55 107 62 3 94 118 116 38 9 21 16 16 98 102 3 1 113 94 112 17 111 92 116 116 64 29 29 17 38 112 116 98 10 78 4 17 94 16 4 110 17 1 95 65 94 110 18 64 116 17 113 15 38 17 111 112 105 38 3 16 105 38 22 16 105 62 62 29 1 110 118 16 16 108 87 17 16 87 17 116 16 19 110 62 16 16 108 87 94 16 63 94 98 16 87 107 116 38 4 111 116 38 38 111 52 4 4 29 42 116 112 94 94 23 94 4 92 75 17 110 94 54 10 62 4 3 116 62 94 94 63 16 98 94 102 70 67 63 110 110 17 83 9 9 38 90 87 87 17 67 116 15 15 38 22 52 38 5 90 87 87 17 87 31 116 94 92 44 38 38 92 90 21 21 99 94 116 17 38 29 3 117 38 9 3 51 111 16 38 91 75 116 116 16 52 17 118 3 78 26 111 16 91 52 17 116 16 111 22 3 3 3 111 111 98 83 79 87 119 119 15 29 3 62 9 4 38 38 94 111 62 4 29 110 110 62 87 62 33 87 16 16 79 29 16 98 15 5 3 87 62 33 38 38 94 
0 1 1
0 4 122
0 0 243
1 5 2
1 3 42
1 2 82
2 1 3
2 3 16
2 2 29
3 1 4
3 2 8
3 3 12
4 5 5
4 2 6
4 3 7
8 2 9
8 3 10
8 5 11
12 3 13
12 2 14
12 5 15
16 0 17
16 3 21
16 4 25
17 2 18
17 3 19
17 0 20
21 4 22
21 5 23
21 1 24
25 2 26
25 5 27
25 4 28
29 0 30
29 2 34
29 4 38
30 2 31
30 3 32
30 0 33
34 4 35
34 5 36
34 1 37
38 1 39
38 3 40
38 2 41
42 2 43
42 5 56
42 4 69
43 2 44
43 1 48
43 0 52
44 0 45
44 5 46
44 4 47
48 2 49
48 5 50
48 3 51
52 2 53
52 0 54
52 1 55
56 5 57
56 1 61
56 0 65
57 0 58
57 2 59
57 4 60
61 1 62
61 2 63
61 0 64
65 5 66
65 0 67
65 1 68
69 5 70
69 2 74
69 4 78
70 1 71
70 3 72
70 2 73
74 1 75
74 3 76
74 5 77
78 2 79
78 3 80
78 5 81
82 1 83
82 3 96
82 5 109
83 1 84
83 5 88
83 3 92
84 3 85
84 5 86
84 2 87
88 3 89
88 5 90
88 2 91
92 3 93
92 5 94
92 2 95
96 0 97
96 4 101
96 3 105
97 0 98
97 5 99
97 2 100
101 3 102
101 5 103
101 4 104
105 2 106
105 4 107
105 5 108
109 0 110
109 4 114
109 5 118
110 5 111
110 2 112
110 3 113
114 5 115
114 3 116
114 4 117
118 5 119
118 0 120
118 1 121
122 5 123
122 3 163
122 2 203
123 0 124
123 2 137
123 1 150
124 0 125
124 2 129
124 1 133
125 5 126
125 4 127
125 2 128
129 4 130
129 5 131
129 2 132
133 2 134
133 3 135
133 1 136
137 2 138
137 0 142
137 5 146
138 2 139
138 5 140
138 4 141
142 3 143
142 1 144
142 4 145
146 0 147
146 4 148
146 1 149
150 0 151
150 2 155
150 1 159
151 4 152
151 1 153
151 5 154
155 5 156
155 1 157
155 0 158
159 5 160
159 4 161
159 2 162
163 4 164
163 2 177
163 5 190
164 2 165
164 5 169
164 4 173
165 2 166
165 5 167
165 3 168
169 5 170
169 2 171
169 3 172
173 2 174
173 5 175
173 3 176
177 0 178
177 1 182
177 2 186
178 4 179
178 5 180
178 2 181
182 5 183
182 2 184
182 4 185
186 3 187
186 1 188
186 5 189
190 0 191
190 1 195
190 5 199
191 4 192
191 2 193
191 5 194
195 2 196
195 5 197
195 4 198
199 3 200
199 1 201
199 2 202
203 1 204
203 3 217
203 5 230
204 3 205
204 5 209
204 2 213
205 3 206
205 4 207
205 5 208
209 5 210
209 4 211
209 3 212
213 3 214
213 5 215
213 0 216
217 4 218
217 3 222
217 0 226
218 4 219
218 5 220
218 3 221
222 1 223
222 5 224
222 0 225
226 2 227
226 1 228
226 5 229
230 5 231
230 4 235
230 0 239
231 1 232
231 3 233
231 0 234
235 4 236
235 3 237
235 5 238
239 2 240
239 1 241
239 3 242
243 5 244
243 3 284
243 2 324
244 4 245
244 1 258
244 2 271
245 1 246
245 4 250
245 2 254
246 2 247
246 3 248
246 1 249
250 4 251
250 3 252
250 1 253
254 5 255
254 4 256
254 1 257
258 1 259
258 4 263
258 2 267
259 3 260
259 4 261
259 5 262
263 1 264
263 5 265
263 0 266
267 5 268
267 1 269
267 4 270
271 3 272
271 1 276
271 5 280
272 0 273
272 4 274
272 2 275
276 0 277
276 3 278
276 4 279
280 5 281
280 4 282
280 1 283
284 5 285
284 4 298
284 1 311
285 3 286
285 4 290
285 5 294
286 4 287
286 0 288
286 1 289
290 5 291
290 4 292
290 3 293
294 0 295
294 5 296
294 3 297
298 1 299
298 4 303
298 5 307
299 2 300
299 5 301
299 1 302
303 3 304
303 0 305
303 5 306
307 4 308
307 3 309
307 1 310
311 1 312
311 4 316
311 5 320
312 3 313
312 0 314
312 5 315
316 2 317
316 5 318
316 4 319
320 0 321
320 1 322
320 2 323
324 4 325
324 3 338
324 1 351
325 1 326
325 4 330
325 3 334
326 3 327
326 5 328
326 1 329
330 2 331
330 0 332
330 3 333
334 1 335
334 2 336
334 0 337
338 5 339
338 4 343
338 2 347
339 3 340
339 1 341
339 2 342
343 5 344
343 4 345
343 2 346
347 0 348
347 2 349
347 4 350
351 1 352
351 4 356
351 3 360
352 2 353
352 0 354
352 3 355
356 1 357
356 2 358
356 0 359
360 2 361
360 4 362
360 0 363
)";


#define tiii tuple<int,int,int>
#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 1e6+10;
const int N = 6;
int tp[mxn];
vector<pii> tree[mxn];
int pw[N+1];
int ep = 0;
const int lim = 10000;
vector<short> param[mxn];
const short C = 6;

int encode(vector<short> v){
	assert(v.size() == N);
	int re = 0;
	for(int i = 0;i<v.size();i++){
		re += pw[i]*v[i];
	}
	return re;
}
vector<short> decode(int k){
	vector<short> re(N);
	for(short i = 0;i<N;i++){
		re[i] = k%N;
		k/=N;
	}
	return re;
}

short f(int opid,int val,bool p = false){
	auto v = param[opid];
	auto arr = decode(val);
	sort(v.begin(),v.begin()+3,[&](short a,short b){return arr[a]<arr[b];});
	assert(arr[v[1]]>arr[v[0]]&&arr[v[2]]>arr[v[1]]);
	short re = -1;
	if(v.back() == 1)re = v[2];
	else if(v.back() == 2)re = v[0];
	else if(v.back() == 3)re = v[1];
	else{
		for(short i = 0;i<3;i++){
			if(arr[v[i]]>arr[v[3]]){
				re = v[i];
				break;
			}
			if(i == 2)re = v[0];
		}
	}
	if(p){
		cerr<<"F: ";for(auto &i:arr)cerr<<i<<' ';cerr<<"::"<<endl;
		for(auto &i:v)cerr<<i<<',';cerr<<endl;
		cerr<<re<<endl;
	}
	return re;
}

void makeparam(){
	int pt = 0;
	for(short i = 0;i<N;i++){
		for(short j = i+1;j<N;j++){
			for(short k = j+1;k<N;k++){
				param[pt] = {i,j,k,1};
				pt++;
				param[pt] = {i,j,k,2};
				pt++;
				param[pt] = {i,j,k,3};
				pt++;
				for(short l = 0;l<N;l++){
					if(l == i||l == j||l == k)continue;
					param[pt] = {i,j,k,l,4};
					pt++;
				}
			}
		}
	}
	cerr<<"PARAM = "<<pt<<endl;
}

void extend(vector<short> &v){
	int now = 0;
	int val = encode(v);
	while(tp[now] != -1){
		int tar = f(tp[now],val);
		for(auto [id,nxt]:tree[now]){
			if(id == tar){
				now = nxt;
				break;
			}
		}
	}
	assert(tp[now] == -1);
	tp[now] = val;
	return;
}

void init(int T) {
	memset(tp,-1,sizeof(tp));
	pw[0] = 1;
	for(int i = 1;i<=N;i++)pw[i] = pw[i-1]*N;
	makeparam();
	stringstream ss(inp);
	int n;
	ss>>n;
	for(int i = 0;i<n;i++)ss>>tp[i];
	for(int i = 1;i<n;i++){
		int a,b,c;
		ss>>a>>b>>c;
		tree[a].push_back(pii(b,c));
	}
	int ptr = n;
	//cout<<"n = "<<n<<endl;
	for(int i = 0;i<n;i++){
		cerr<<i<<endl;
		assert(tp[i] != -1);
		if(tree[i].empty()){
			auto tv = param[tp[i]];
			tree[i].push_back(pii(tv[0],ptr++));
			tree[i].push_back(pii(tv[1],ptr++));
			tree[i].push_back(pii(tv[2],ptr++));
		}
	}
	cerr<<"TREE IN! "<<endl;
	vector<short> perm;
	for(int i = 0;i<N;i++)perm.push_back(i);
	do{
		extend(perm);
	}while(next_permutation(perm.begin(),perm.end()));
}

int ask(int opid){
	assert(opid>=0);
	auto v = param[opid];
	//cerr<<"ASK: ";for(auto &i:v)cerr<<i<<':';
	if(v.back() == 1)return getHeaviest(v[0]+1,v[1]+1,v[2]+1)-1;
	else if(v.back() == 2)return getLightest(v[0]+1,v[1]+1,v[2]+1)-1;
	else if(v.back() == 3)return getMedian(v[0]+1,v[1]+1,v[2]+1)-1;
	else return getNextLightest(v[0]+1,v[1]+1,v[2]+1,v[3]+1)-1;
}

void orderCoins() {
	int now = 0;
	while(!tree[now].empty()){
		//cerr<<tp[now]<<"::";
		int tmp = ask(tp[now]);
		//cerr<<":::"<<tmp<<endl;
		for(auto &j:tree[now]){
			if(j.fs == tmp){
				now = j.sc;
				break;
			}
		}
	}
	//cerr<<"f(0,tp[now]): "<<TREE::f(0,tp[now],true)<<endl;
	auto tmp = decode(tp[now]);
	//cerr<<"TMP: ";for(auto &i:tmp)cerr<<i<<' ';cerr<<endl;
	auto ans = tmp;
	for(int i = 0;i<N;i++)ans[tmp[i]] = i;
	//cerr<<"ANSWEr: ";for(auto &i:ans)cerr<<i<<' ';cerr<<endl;
	int re[N];
	for(int i = 0;i<N;i++)re[i] = ans[i]+1;
	answer(re);
	return;
}

Compilation message (stderr)

scales.cpp: In function 'int encode(std::vector<short int>)':
scales.cpp:394:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<short int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  394 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~
scales.cpp: In function 'std::vector<short int> decode(int)':
scales.cpp:402:12: warning: conversion from 'int' to '__gnu_cxx::__alloc_traits<std::allocator<short int>, short int>::value_type' {aka 'short int'} may change value [-Wconversion]
  402 |   re[i] = k%N;
      |           ~^~
scales.cpp: In function 'short int f(int, int, bool)':
scales.cpp:428:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  428 |   for(auto &i:v)cerr<<i<<',';cerr<<endl;
      |   ^~~
scales.cpp:428:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  428 |   for(auto &i:v)cerr<<i<<',';cerr<<endl;
      |                              ^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:501:39: warning: conversion from 'int' to 'std::vector<short int>::value_type' {aka 'short int'} may change value [-Wconversion]
  501 |  for(int i = 0;i<N;i++)perm.push_back(i);
      |                                       ^
scales.cpp:473:15: warning: unused parameter 'T' [-Wunused-parameter]
  473 | void init(int T) {
      |           ~~~~^
scales.cpp: In function 'void orderCoins()':
scales.cpp:534:38: warning: conversion from 'int' to '__gnu_cxx::__alloc_traits<std::allocator<short int>, short int>::value_type' {aka 'short int'} may change value [-Wconversion]
  534 |  for(int i = 0;i<N;i++)ans[tmp[i]] = i;
      |                                      ^

• Subtask 1: 100 / 100