Submission #286209

#	Time	Username	Problem	Language	Result	Execution time	Memory
286209		user202729	Toy Train (IOI17_train)	C++17	10 / 100	11 ms	896 KiB

train

// moreflags=grader.cpp
//
// 13
// still unproven.
// 
#include "train.h"

std::vector<int> who_wins(std::vector<int> a, std::vector<int> r, std::vector<int> u, std::vector<int> v) {
	if(a.size()>15) return {};
	std::vector<int> adjacent(a.size());
	for(int index=0; index<(int)u.size(); ++index){
		adjacent[u[index]]|=1<<v[index];
	}

	int noChargeMask=0;
	for(int node=0; node<(int)r.size(); ++node)
		if(not r[node])
			noChargeMask|=1<<node;

	auto const contains=[&](int large, int small){ return (large&small)==small; };

	int bwin{};
	for(int _=0; _<(int)a.size()+1; ++_){
		for(int mask=noChargeMask; mask; mask=(mask-1)&noChargeMask){
			for(int node=0; node<(int)a.size(); ++node)
				if(mask>>node&1){
					if(a[node]){
						if(not contains(mask|bwin, adjacent[node]))
							goto next_mask;
					}else{
						if(((mask|bwin)&adjacent[node])==0)
							goto next_mask;
					}
				}
			bwin|=mask;
next_mask:;
		}

		for(int node=0; node<(int)a.size(); ++node)
			if(a[node]){
				if(contains(bwin, adjacent[node])) bwin|=1<<node;
			}else{
				if((bwin&adjacent[node])!=0) bwin|=1<<node;
			}
	}

	std::vector<int> result(a.size());
	for(int node=0; node<(int)a.size(); ++node)
		result[node]=not(bwin>>node&1);
	return result;
}

• Subtask 1: 0 / 5
• Subtask 2: 10 / 10
• Subtask 3: 0 / 11
• Subtask 4: 0 / 11
• Subtask 5: 0 / 12
• Subtask 6: 0 / 51