oj.uz

Submission #31174

# Submission time Handle Problem Language Result Execution time Memory
31174 2017-08-12T12:38:30 Z cscandkswon Scales (IOI15_scales) C++14
0 / 100
 13 ms 2068 KB 
#include "scales.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXQ=120;
const int MAXP=720;

struct Question{
	int type, a, b, c, d;
} Q[MAXQ];

struct Permutation{
	int A[7];
} P[MAXP];

int order[5000];

int getL(Permutation list, int a, int b, int c){
	if(list.A[a]<list.A[b] && list.A[a]<list.A[c]) return 0;
	else if(list.A[b]<list.A[c]) return 1;
	return 2;
}

int getH(Permutation list, int a, int b, int c){
	if(list.A[a]>list.A[b] && list.A[a]>list.A[c]) return 0;
	else if(list.A[b]>list.A[c]) return 1;
	return 2;
}

int getM(Permutation list, int a, int b, int c){
	if(min(list.A[b], list.A[c])<list.A[a]&&list.A[a]<max(list.A[b], list.A[c])) return 0;
	else if(min(list.A[a], list.A[c])<list.A[b]&&list.A[b]<max(list.A[a], list.A[c])) return 1;
	return 2;
}

int getN(Permutation list, int a, int b, int c, int d){
	int x=(list.A[d]<list.A[a]), y=(list.A[d]<list.A[b]), z=(list.A[d]<list.A[c]);
	if(x&&y&&z) return getL(list, a, b, c);
	else if(x&&y){
		if(list.A[a]<list.A[b]) return 0;
		else return 1;
	}
	else if(x&&z){
		if(list.A[a]<list.A[c]) return 0;
		else return 2;
	}
	else if(y&&z){
		if(list.A[b]<list.A[c]) return 1;
		return 2;
	}
	else if(x) return 0;
	else if(y) return 1;
	else if(z) return 2;
	else return getL(list, a, b, c);
}

int makeorder(int lev, vector<int> list, int idx){
	if(lev==6){
		if(list.size()==1)
			order[idx]=list[0];
		return 1;
	}
	int i, j, rv, cnt[3]={0};
	for(i=0; i<MAXQ; i++){
		cnt[0]=cnt[1]=cnt[2]=0;
		for(j=0; j<list.size(); j++){
			if(Q[i].type==1) rv=getL(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
			else if(Q[i].type==2) rv=getH(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
			else if(Q[i].type==3) rv=getM(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
			else rv=getN(P[list[j]], Q[i].a, Q[i].b, Q[i].c, Q[i].d);
			cnt[rv]++;
		}
		if(max(cnt[0], max(cnt[1], cnt[2]))-min(cnt[0], min(cnt[1], cnt[2]))<=1){
			vector<int> lst[3];
			for(j=0; j<list.size(); j++){
				if(Q[i].type==1) rv=getL(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
				else if(Q[i].type==2) rv=getH(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
				else if(Q[i].type==3) rv=getM(P[list[j]], Q[i].a, Q[i].b, Q[i].c);
				else rv=getN(P[list[j]], Q[i].a, Q[i].b, Q[i].c, Q[i].d);
				lst[rv].push_back(list[j]);
			}
			rv=makeorder(lev+1, lst[0], idx*3-1);
			if(!rv) continue;
			rv=makeorder(lev+1, lst[1], idx*3);
			if(!rv) continue;
			rv=makeorder(lev+1, lst[2], idx*3+1);
			if(!rv) continue;
			order[idx]=i;
			return 1;
		}
	}
	return 0;
}

void init(int T) {
	int i, j, k, l, idx=0, A[6];
	for(i=1; i<=6; i++){
		for(j=i+1; j<=6; j++){
			for(k=j+1; k<=6; k++){
				Q[idx].type=1, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
				Q[idx].type=2, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
				Q[idx].type=3, Q[idx].a=i, Q[idx].b=j, Q[idx++].c=k;
				for(l=1; l<=6; l++) if(l!=i && l!=j && l!=k){
					Q[idx].type=4, Q[idx].a=i, Q[idx].b=j, Q[idx].c=k, Q[idx++].d=l;
				}
			}
		}
	}
	idx=0;
	for(i=1; i<=6; i++) A[i]=i;
	do{
		for(i=1; i<=6; i++) P[idx].A[i]=A[i];
		idx++;
	}while(next_permutation(A+1, A+7));
	vector<int> vec;
	for(i=0; i<MAXP; i++) vec.push_back(i);
	makeorder(0, vec, 1);
}

void orderCoins() {
	int i, idx=1, rv;
	for(i=0; i<6; i++){
		if(Q[order[idx]].type==1)
			rv=getLightest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
		else if(Q[order[idx]].type==2)
			rv=getHeaviest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
		else if(Q[order[idx]].type==3)
			rv=getMedian(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c);
		else
			rv=getNextLightest(Q[order[idx]].a, Q[order[idx]].b, Q[order[idx]].c, Q[order[idx]].d);
		if(rv==Q[order[idx]].a) rv=0;
		else if(rv==Q[order[idx]].b) rv=1;
		else rv=2;
		if(rv==0) idx=idx*3-1;
		else if(rv==1) idx=idx*3;
		else idx=idx*3+1;
	}
	idx=order[idx];
	int ans[6];
	for(i=1; i<=6; i++){
		ans[P[idx].A[i]-1]=i;
	}
	answer(ans);
}

Compilation message

scales.cpp: In function 'int makeorder(int, std::vector<int>, int)':
scales.cpp:65:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0; j<list.size(); j++){
             ^
scales.cpp:74:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0; j<list.size(); j++){
              ^
scales.cpp: At global scope:
scales.cpp:94:15: warning: unused parameter 'T' [-Wunused-parameter]
 void init(int T) {
               ^

Subtask #1
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
2 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
3 Runtime error 13 ms 2068 KB Execution killed because of forbidden syscall writev (20)
4 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 13 ms 2068 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
11 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
12 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
13 Runtime error 13 ms 2068 KB Execution killed because of forbidden syscall writev (20)
14 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
15 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
16 Runtime error 13 ms 2068 KB Execution killed because of forbidden syscall writev (20)
17 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
18 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
19 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
20 Runtime error 13 ms 2068 KB Execution killed because of forbidden syscall writev (20)
21 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
22 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
23 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
24 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
25 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
26 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
27 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
28 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
29 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
30 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
31 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
32 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
33 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
34 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
35 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
36 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
37 Runtime error 13 ms 2068 KB Execution killed because of forbidden syscall writev (20)
38 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
39 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)
40 Runtime error 9 ms 2068 KB Execution killed because of forbidden syscall writev (20)