#include <bits/stdc++.h>
#include "Alicelib.h"
using namespace std;
#define maxn 1010
#define pii pair<int, int>
int e[12]; //store the indices for the extra guys
int deg[12]; //store the degrees for each of the extras
vector<pii> edges;
void Alice(int N, int M, int A[], int B[]) {
if (N == 1) {
//handle this case uniquely
InitG(1, 0);
return;
}
if (N == 2) {
InitG(N, M);
if (M == 1) {
MakeG(0, 0, 1);
}
return;
}
//lol, need to push back original edges or something
for (int i = 0; i < M; i++) {
edges.push_back(pii(A[i], B[i]));
}
if (N == 3) {
bool cad[3][3]; //current adjacent
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cad[i][j] = false;
}
}
for (int i = 0; i < M; i++) {
cad[A[i]][B[i]] = true;
cad[B[i]][A[i]] = true;
}
if (cad[0][1] && cad[0][2] && cad[1][2]) {
InitG(11, 0);
return;
}
if (cad[0][1] && cad[1][2]) {
InitG(10, 0);
return;
}
if (cad[0][2] && cad[1][2]) {
InitG(9, 0);
return;
}
if (cad[0][1] && cad[0][2]) {
InitG(8, 0);
return;
}
if (cad[0][2]) {
InitG(7, 0);
return;
}
if (cad[1][2]) {
InitG(6, 0);
return;
}
if (cad[0][1]) {
InitG(5, 0);
return;
}
InitG(4, 0);
return;
}
//all special cases finished
for (int i = 0; i < 12; i++) {
e[i] = N + i; //just store it
}
for (int i = 0; i < N; i++) {
edges.push_back(pii(e[11], i));
}
for (int i = 0; i < N; i++) {
//connect me to everythig that one greater than me stores (oops)
for (int j = 0; j < 10; j++) {
if ( (i + 1) & ( 1 << j)) {
edges.push_back(pii(e[j], i));
deg[j]++;
}
}
}
edges.push_back(pii(e[11], e[10]));
for (int i = 0; i < 9; i++) {
if (i == 10) continue;
edges.push_back(pii(e[10], e[i]));
}
if (N != 9) edges.push_back(pii(e[10], e[9]));
else edges.push_back(pii(e[9], e[10]));
for (int i = 1; i < 10; i++) { //create the change
edges.push_back(pii(e[i-1], e[i]));
}
InitG(N+12, edges.size());
for (int i = 0; i < edges.size(); i++) {
MakeG(i, edges[i].first, edges[i].second);
}
/*
cout << "ALICE EDGES" << endl;
for (pii vp : edges) {
cout << "--------> " << vp.first << " " << vp.second << endl;
}
cout << endl << endl;
*/
//i think this is finished
}
//call InitG with some number of nodes and edges
//cakk MakeG with pos, a, and b
#include <bits/stdc++.h>
#include "Boblib.h"
using namespace std;
#define edges this_is_a_bad_variable_name
#define e this_is_a_bad_variable_name2
#define dec this_is_a_bad_variable_name3
#define deg this_is_a_bad_variable_name4
#define pii pair<int, int>
//adding macros to make it compile locally
vector<pii> edges; //this is where we store the answers
int e[12];
int dec[1100]; //decode the nodes (what they are now vs what they should be)
int enc[1100]; //encode the nodes (opp of above)
int deg[1100];
vector<vector<int>> adj(1100);
void special(int v) {
//figure it out for 3
if (v == 4) {
InitMap(3, 0);
return;
}
if (v == 5) {
InitMap(3, 1);
MakeMap(0, 1);
return;
}
if (v == 6) {
InitMap(3, 1);
MakeMap(1, 2);
return;
}
if (v == 7) {
InitMap(3, 1);
MakeMap(0, 2);
return;
}
if (v == 8) {
InitMap(3, 2);
MakeMap(0, 1);
MakeMap(0, 2);
return;
}
if (v == 9) {
InitMap(3, 2);
MakeMap(0, 2);
MakeMap(1, 2);
return;
}
if (v == 10) {
InitMap(3, 2);
MakeMap(0, 1);
MakeMap(1, 2);
return;
}
if (v == 11) {
InitMap(3, 3);
MakeMap(0, 1);
MakeMap(0, 2);
MakeMap(1, 2);
}
}
void Bob(int V, int U, int C[], int D[]) {
// cout << "V: " << V << endl;
if (V == 1) {
InitMap(1, 0);
return;
}
if (V == 2) {
InitMap(V, U);
if (U == 1) MakeMap(0, 1);
return;
}
if (V < 12) {
special(V);
return;
}
//special cases are finished
int n = V-12;
for (int i = 0; i < 12; i++) {
e[i] = n+i; //same scheme as in Alice
}
//first we need to find the node that is e11, connected to all n things
// cout << "ORIGINAL EDGES" << endl;
for (int i = 0; i < U; i++) {
adj[C[i]].push_back(D[i]);
adj[D[i]].push_back(C[i]);
deg[C[i]]++;
// deg[D[i]]++;
// if (C[i] == 14 || D[i] == 14) cout << "** ";
// cout << " " << C[i] << " " << D[i] << endl;
}
// cout << endl << endl;
int e11 = -1; //find this boy
for (int i = 0; i < V; i++) {
if (deg[i] == n+1) { //connected to all original plus the dummy
e11 = i;
}
}
// cout << "e11 deg: " << deg[e11] << endl;
// cout << "e11: " << e11 << endl;
dec[e11] = e[11];
enc[e[11]] = e11;
//now that we have the node, we can just separate into o group and others
vector<int> ogroup;
set<int> og;
vector<int> ext;
set<int> isext;
set<int> seen;
seen.insert(e11);
for (int val : adj[e11]) {
seen.insert(val);
}
for (int i = 0; i < V; i++) {
if (seen.find(i) == seen.end()) {
// cout << i << " is an extra " << endl;
ext.push_back(i);
isext.insert(i);
}
}
int dummy = -1; //find the guy with degree one from the extras
for (int val : seen) {//look for the dummy
int ed = 0; //extra degree
for (int v2 : adj[val]) {
if (isext.count(v2) > 0) ed++;
}
if (ed == 10) {
//connect to 0 throuh 9
dummy = val;
}
// cout << val << " ----- " << adj[val].size() << " " << ed << endl;
}
// cout << endl;
// cout << "dummy: " << dummy << endl;
for (int i = 0; i < V; i++) {
if (i == dummy || i == e11 || isext.count(i)) continue;
ogroup.push_back(i);
og.insert(i);
}
vector<pii> d1e;
for (int val : ext) {
int ed = 0;
for (int v2 : adj[val]) {
if (isext.count(v2) > 0) {
ed++;
}
}
if (ed == 1) {
//is an endpoint
d1e.push_back(pii(adj[val].size()-1, val));
}
}
// cout << "SZ: " << d1e.size() << endl;
sort(d1e.begin(), d1e.end());
dec[dummy] = e[10];
enc[e[10]] = dummy;
map<int, int> bm; //bitmask map
// cout << "original Nodes: ";
// for (int val : ogroup) cout << val << " ";
// cout << endl;
int cur = d1e[1].second;
// cout << "CHAIN: " << cur << " ";
bm[cur] = 0;
for (int i = 1 ; i < 10; i++) {
//find the next thing
seen.insert(cur);
int nx = -1;
for (int val : adj[cur]) {
if (seen.find(val) == seen.end()) {
//is an extra vertex
nx = val;
break;
}
}
if (nx == -1) break; //nothing more to see here
dec[nx] = e[i];
enc[e[i]] = nx;
// if (bm.count(nx) == 0) cout << "NOOOO" << endl;
bm[nx] = i;
cur = nx; //last part of the loop
// cout << cur << " ";
}
// cout << endl;
for (int val : ogroup) {
int cv = 0;
for (int nx : adj[val]) {
if (og.find(nx) != og.end() || nx == e11) continue;
// cout << val << ": chaining to: " << nx << endl;
// if (bm.count(nx) == 0) cout << " WHYYYYYY" << endl;
int nv = bm[nx];
cv += (1 << nv);
}
// cout << val << " gets: " << cv-1 << endl;
dec[val] = cv-1; //subtract 1 b/c 0-indexed
}
for (int val : ogroup) {
for (int nx : adj[val]) {
if (og.find(nx) != og.end() && dec[val] < dec[nx]) {
edges.push_back(pii(dec[val], dec[nx])); //decode both
// cout << "draws an edge from "
// << dec[val] << " to " << dec[nx] << endl;
}
}
}
//everything finished
InitMap(n, edges.size());
for (pii vp : edges) {
MakeMap(vp.first, vp.second);
}
}
//Initmap with n nodes and e edges
Compilation message
Alice.cpp: In function 'void Alice(int, int, int*, int*)':
Alice.cpp:103:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < edges.size(); i++) {
~~^~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
10 ms |
6728 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
10 ms |
6728 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
794 ms |
34668 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
