Submission #745107

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
745107	2023-05-19T12:05:41 Z	sword060	Hiperkocka (COCI21_hiperkocka)	C++17	0 / 110	1000 ms	3376 KB

Main

#include <bits/stdc++.h>
using namespace std;
const int N=1<<16;
int x;
vector<int>all;
set<int>v[N];
set<vector<int>>fnd;
vector<vector<int>>ans;
set<pair<int,int>>edges;
int main(){
  ios::sync_with_stdio(0);cin.tie(0);
  srand(time(NULL));
  cin>>x;
  for(int i=1;i<=x;i++){
    int l,r;cin>>l>>r;
    v[l].insert(r);v[r].insert(l);
  }
  for(int i=0;i<(1<<x);i++)
    all.push_back(i);
  for(int rep=0;rep<(1<<20);rep++){
    random_shuffle(all.begin(),all.end());
    vector<int>cur;
    bool f=1;
    for(int i=0;i<=x;i++){
      cur.push_back(all[i]);
      for(int j=i+1;j<=x;j++){
      	int m=all[i]^all[j];
        int f1=v[i].count(j)+v[j].count(i),f2=(m==1||((m&(m-1))==0));
        if((f1>0)^f2)f=0;
        if(f2&&edges.count({i,j}))f=0;
      }
    }
    vector<int>xd=cur;
    sort(xd.begin(),xd.end());
    f&=(fnd.find(xd)==fnd.end());
    if(f){
      fnd.insert(xd);
      ans.push_back(cur);
      for(int i=1;i<=x;i++)
      	for(int j=i+1;j<=x;j++){
      		int m=all[i]^all[j];
      		if(m==1||((m&(m-1))==0))edges.insert({i,j});
      	}
    }
    if(fnd.size()==(1<<(x-1)))break;
  }
  cout<<(ans.size())<<"\n";
  for(auto i:ans){
    for(auto j:i)cout<<j<<" ";
    cout<<"\n";
  }
  return 0;
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:45:18: warning: comparison of integer expressions of different signedness: 'std::set<std::vector<int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |     if(fnd.size()==(1<<(x-1)))break;
      |        ~~~~~~~~~~^~~~~~~~~~~~

Subtask #1

0.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Partially correct	245 ms	3284 KB	Output is partially correct
2	Partially correct	366 ms	3376 KB	Output is partially correct
3	Partially correct	606 ms	3376 KB	Output is partially correct
4	Execution timed out	1071 ms	3284 KB	Time limit exceeded
5	Halted	0 ms	0 KB	-