Submission #529385

Source Code Expand

#include<iostream>
#include<vector>
#include<algorithm>
#include<cassert>
using namespace std;
typedef long long ll;

#define REP(i, n) for(int i=0;i<(int)n;i++)
#define REPS(i, n) for(int i=1;i<=(int)n;i++)
int w, h, r, a;

vector<int> solve(vector<int> v){
	REP(s, 1<<w){
		vector<int> cur = v;
		vector<int> ans(h);
		ans[0] = s;
		REP(j, w)if(s&(1<<j)){
			cur[0] ^= 1<<(j+0);
			if(j+1 < w) cur[0] ^= 1<<(j+1);
			if(0 < j) cur[0] ^= 1<<(j-1);
			if(1 < h) cur[1] ^= 1<<(j);
		}
		REPS(i, h-1)REP(j, w)if(cur[i-1]&(1<<j)){
			ans[i] ^= 1<<j;
			cur[i-1] ^= (1<<j);
			cur[i] ^= 1<<(j+0);
			if(j+1 < w) cur[i] ^= 1<<(j+1);
			if(0 < j) cur[i] ^= 1<<(j-1);
			if(i+1 < h) cur[i+1] ^= 1<<(j);
		}
		if(cur[h-1] % (1<<w) == 0) return ans;
	}
	assert(false);
}

int main(){
	cin >> w >> h >> r >> a; r--;
	assert(w<=10 && w<=10);
	vector<int> v(h);
	REP(i, a){
		int y, b;
		cin >> y >> b; y--;
		REP(j, b){
			int x;
			cin >> x; x--;
			v[y] |= 1<<x;
			
		}
	}
	auto res = solve(v);
	cout << __builtin_popcount(res[r]);
	REP(i, w) if(res[r] & (1<<i))
		cout << " " << i + 1;
	cout << endl;
	return 0;
}

Submission Info

Submission Time
Task D - IOI
User Mi_kugi
Language C++11 (GCC 4.9.2)
Score 10
Code Size 1161 Byte
Status RE
Exec Time 307 ms
Memory 1260 KiB

Judge Result

Set Name subtask1 subtask2 subtask3 subtask4 subtask5 subtask6
Score / Max Score 10 / 10 0 / 25 0 / 10 0 / 25 0 / 15 0 / 15
Status
AC × 10
RE × 10
RE × 10
RE × 10
RE × 10
RE × 10
Set Name Test Cases
subtask1 subtask1_01, subtask1_02, subtask1_03, subtask1_04, subtask1_05, subtask1_06, subtask1_07, subtask1_08, subtask1_09, subtask1_10, killer1, killer2, killer3
subtask2 subtask2_01, subtask2_02, subtask2_03, subtask2_04, subtask2_05, subtask2_06, subtask2_07, subtask2_08, subtask2_09, subtask2_10, killer1, killer2, killer3
subtask3 subtask3_01, subtask3_02, subtask3_03, subtask3_04, subtask3_05, subtask3_06, subtask3_07, subtask3_08, subtask3_09, subtask3_10, killer1, killer2, killer3
subtask4 subtask4_01, subtask4_02, subtask4_03, subtask4_04, subtask4_05, subtask4_06, subtask4_07, subtask4_08, subtask4_09, subtask4_10, killer1, killer2, killer3
subtask5 subtask5_01, subtask5_02, subtask5_03, subtask5_04, subtask5_05, subtask5_06, subtask5_07, subtask5_08, subtask5_09, subtask5_10, killer1, killer2, killer3
subtask6 subtask6_01, subtask6_02, subtask6_03, subtask6_04, subtask6_05, subtask6_06, subtask6_07, subtask6_08, subtask6_09, subtask6_10, killer1, killer2, killer3
Case Name Status Exec Time Memory
killer1.txt AC 33 ms 1180 KiB
killer2.txt AC 30 ms 1232 KiB
killer3.txt AC 32 ms 1260 KiB
subtask1_01 AC 33 ms 1244 KiB
subtask1_02 AC 31 ms 1076 KiB
subtask1_03 AC 34 ms 1180 KiB
subtask1_04 AC 33 ms 1176 KiB
subtask1_05 AC 32 ms 1080 KiB
subtask1_06 AC 34 ms 1172 KiB
subtask1_07 AC 34 ms 1172 KiB
subtask1_08 AC 33 ms 1076 KiB
subtask1_09 AC 35 ms 1172 KiB
subtask1_10 AC 33 ms 1240 KiB
subtask2_01 RE 307 ms 1056 KiB
subtask2_02 RE 285 ms 1044 KiB
subtask2_03 RE 286 ms 1084 KiB
subtask2_04 RE 287 ms 1144 KiB
subtask2_05 RE 283 ms 976 KiB
subtask2_06 RE 286 ms 1072 KiB
subtask2_07 RE 294 ms 1044 KiB
subtask2_08 RE 283 ms 984 KiB
subtask2_09 RE 285 ms 1048 KiB
subtask2_10 RE 292 ms 1040 KiB
subtask3_01 RE 294 ms 984 KiB
subtask3_02 RE 290 ms 980 KiB
subtask3_03 RE 301 ms 1052 KiB
subtask3_04 RE 286 ms 1040 KiB
subtask3_05 RE 286 ms 1012 KiB
subtask3_06 RE 286 ms 984 KiB
subtask3_07 RE 286 ms 1036 KiB
subtask3_08 RE 284 ms 1040 KiB
subtask3_09 RE 292 ms 1052 KiB
subtask3_10 RE 284 ms 1148 KiB
subtask4_01 RE 285 ms 1044 KiB
subtask4_02 RE 296 ms 1040 KiB
subtask4_03 RE 284 ms 1044 KiB
subtask4_04 RE 285 ms 980 KiB
subtask4_05 RE 283 ms 1008 KiB
subtask4_06 RE 291 ms 1040 KiB
subtask4_07 RE 293 ms 976 KiB
subtask4_08 RE 282 ms 1048 KiB
subtask4_09 RE 284 ms 1092 KiB
subtask4_10 RE 287 ms 1044 KiB
subtask5_01 RE 289 ms 1124 KiB
subtask5_02 RE 287 ms 1044 KiB
subtask5_03 RE 287 ms 1140 KiB
subtask5_04 RE 290 ms 1044 KiB
subtask5_05 RE 294 ms 1048 KiB
subtask5_06 RE 293 ms 1044 KiB
subtask5_07 RE 298 ms 1044 KiB
subtask5_08 RE 300 ms 1048 KiB
subtask5_09 RE 301 ms 1052 KiB
subtask5_10 RE 300 ms 1040 KiB
subtask6_01 RE 285 ms 1068 KiB
subtask6_02 RE 284 ms 1060 KiB
subtask6_03 RE 285 ms 1140 KiB
subtask6_04 RE 283 ms 1036 KiB
subtask6_05 RE 290 ms 1044 KiB
subtask6_06 RE 286 ms 1044 KiB
subtask6_07 RE 285 ms 1048 KiB
subtask6_08 RE 285 ms 1044 KiB
subtask6_09 RE 305 ms 1148 KiB
subtask6_10 RE 293 ms 980 KiB