blah.cpp (2958B)
1 #include <cstdio> 2 #include <vector> 3 #include <algorithm> 4 5 using namespace std; 6 int s,a,b,c,d,e,h,n; 7 vector<int> r1,r2,c1,c2,size,ham; 8 vector<vector<int> > G; 9 10 int qual(int x) { 11 return (c1[x] - c2[x]) * (c1[x] - c2[x]) 12 + (r1[x] - r2[x]) * (r1[x] - r2[x]); 13 } 14 15 //avant 16 bool compare_vect(int x, int y){ 17 if(size[x] != size[y]) 18 return size[x]>size[y]; 19 if(ham[x] != ham[y]) 20 return ham[x] < ham[y]; 21 if(r1[x]!=r1[y]) 22 return r1[x]<r1[y]; 23 return c1[x]<c1[y]; 24 } 25 26 //bool compare_vect(int x, int y){ 27 // if(G[x].size()==G[y].size()){ 28 // return size[x]<size[y]; 29 // } else { 30 // return G[x].size()<G[y].size(); 31 // } 32 //} 33 34 vector<int> ids; 35 36 37 int optimize(vector<bool> &taken, vector<int> &sortie) { 38 int score = 0; 39 for(unsigned int i=0;i<G.size();i++){ 40 if(taken[ids[i]])continue; 41 //printf("je prends %d\n", ids[i]); 42 score += size[ids[i]]; 43 sortie.push_back(ids[i]); 44 for(unsigned int j = 0; j < G[ids[i]].size(); j++){ 45 // printf("j'exclus %d\n", G[ids[i]][j]); 46 taken[G[ids[i]][j]]=true; 47 } 48 } 49 return score; 50 } 51 52 int main(){ 53 //srand(42); 54 scanf("%d",&n); 55 G.resize(n); 56 for(int x=0;x<n;x++){ 57 scanf("%d%d%d%d%d%d%d",&s, &a, &b, &c, &d, &h, &e); 58 r1.push_back(a); 59 c1.push_back(b); 60 r2.push_back(c); 61 c2.push_back(d); 62 ham.push_back(h); 63 size.push_back(s); 64 for(int y=0;y<e;y++){ 65 int aa; 66 scanf("%d", &aa); 67 G[x].push_back(aa); 68 // if (r1[x] == 0 && c1[x] == 0 && r2[x] == 1 && c2[x] == 8) { 69 // printf("COUCOU %d\n", aa); 70 // if (r1[aa] == 0 && c1[aa] == 0 && r2[aa] == 1 && c2[aa] == 9) { 71 // printf("YESSS\n"); 72 // } 73 // } 74 } 75 } 76 77 vector<bool> taken(G.size(),false); 78 vector<int> sortie; 79 ids.resize(G.size()); 80 for (unsigned i = 0; i < G.size(); i++) { 81 ids[i]=i; 82 } 83 sort(ids.begin(),ids.end(),compare_vect); 84 85 int score = optimize(taken, sortie); 86 87 printf("SCORE %d\n", score); 88 89 // for (unsigned int ncase = 0; ncase < 1000; ncase++) { 90 // int val = 0; 91 // vector<int> rm; 92 // 93 // for (int i= 0 ; i < 10; i++) { 94 // int nn = rand() % G.size(); 95 // if (taken[ids[nn]]) { 96 // taken[ids[nn]] = false; 97 // val -= size[ids[nn]]; 98 // rm.push_back(nn); 99 // } 100 // } 101 // vector<int> myn; 102 // val += optimize(taken, myn); 103 // if (val < 0) { 104 // // baad 105 // for (unsigned int j= 0; j < myn.size(); j++) { 106 // taken[myn[j]] = false; 107 // } 108 // for (unsigned int j= 0; j < rm.size(); j++) { 109 // taken[ids[rm[j]]] = true; 110 // } 111 // } else { 112 // sortie.clear(); 113 // for (unsigned int j = 0; j < G.size(); j++) { 114 // if (!taken[ids[j]]) { 115 // sortie.push_back(ids[j]); 116 // } 117 // } 118 // } 119 // } 120 121 // output 122 printf("%d\n", (int) sortie.size()); 123 for (unsigned i = 0; i < sortie.size(); i++) { 124 printf("%d %d %d %d\n", r1[sortie[i]], c1[sortie[i]], r2[sortie[i]]-1, c2[sortie[i]]-1); 125 } 126 127 return 0; 128 129 130 }