제출 #1289676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1289676		mefe123	Norela (info1cup18_norela)	C++20	75 / 100	1095 ms	580 KiB

norela

		#include <iostream> 
		#include <vector> 
		#include <string> 
		#include <algorithm>
		#include <cmath> 
		#include <map>
		#include <set>
		#include <queue>	
		#include <stack>
		#include <unordered_map>
		#include <unordered_set>
		#include <bitset>
		#include <numeric>
		#include <functional>
		#include <iomanip>
		#include <sstream>

		#define int long long

		using namespace std;
		vector<int> acevap;
		int cevaps=1e9;
		void dene(int id,vector<int> sb,vector<vector<int>> &b,int m,int n,int sayac,vector<int> cevap){
			if(id==m){
				int kontrol=1;
				for(auto go:sb){
					if(go==0){
						kontrol=0;
					}
				}
				if(kontrol==1&&cevap.size()<cevaps){
					cevaps=cevap.size();
					acevap=cevap;
				}
				else if(cevap.size()==cevaps){
					for(int i=0;i<cevap.size();i++){
						if(acevap<cevap){
							kontrol=0;
							break;
							
						}
					}
					if(kontrol==1){
						cevaps=cevap.size();
						acevap=cevap;
					}
				}
				return;
			}
			

			dene(id+1,sb,b,m,n,sayac,cevap);
			vector<int> ysb1=sb;
			for(int i=0;i<n;i++){
				ysb1[i]=ysb1[i]^b[id][i];
			}
			cevap.push_back(id);
			dene(id+1,ysb1,b,m,n,sayac+1,cevap);
		}
		
		void solve(int n,int m){
			vector<vector<int>> b(m,vector<int>(n,0));
			for(int i=0;i<m;i++){
				int x;
				cin>>x;
				for(int j=0;j<x;j++){
					int v;
					cin>>v;
					b[i][v-1]=1;
				}
			}
			vector<int> sb(n,0);
			vector<int> cevap;
			dene(0,sb,b,m,n,0,cevap);
			if(acevap.size()==0){
				cout<<-1<<endl;
			}
			else{
				cout<<acevap.size()<<endl;
				for(int i=0;i<acevap.size();i++){
					cout<<acevap[i]+1<<" ";
				}
			}
		}

		signed main(){
			int t=1;
			//cin>>t;
			while(t--){
				int n,m;
				cin>>n>>m;
				solve(n,m);
			}
		}

• Subtask 1: 20 / 20
• Subtask 2: 30 / 30
• Subtask 3: 25 / 25
• Subtask 4: 0 / 25