ens-ulm-1-2015

commit 7abc5c8e95763cb60bc9751aba8650802c8bb1f0
parent df6466c226541954a968ce6884a2eae200800503
Author: Antoine Amarilli <a3nm@a3nm.net>
Date:   Fri, 27 Mar 2015 22:19:26 +0100

best

Diffstat:
testing/blah.cpp
 | 
50
++++++++++++++++++++++++++++++++++----------------

1 file changed, 34 insertions(+), 16 deletions(-)
diff --git a/testing/blah.cpp b/testing/blah.cpp
@@ -7,6 +7,11 @@ int s,a,b,c,d,e,n;
 vector<int> r1,r2,c1,c2,size;
 vector<vector<int> > G;
 
+int qual(int x) {
+  return (c1[x] - c2[x]) * (c1[x] - c2[x])
+      +  (r1[x] - r2[x]) * (r1[x] - r2[x]);
+}
+
 //avant
 bool compare_vect(int x, int y){
     if(size[x] == size[y]){
@@ -24,6 +29,23 @@ bool compare_vect(int x, int y){
 //    }
 //}
 
+vector<int> ids;
+
+
+int optimize(vector<bool> &taken, vector<int> &sortie) {
+  int score = 0;
+  for(unsigned int i=0;i<G.size();i++){
+    if(taken[ids[i]])continue;
+    //printf("je prends %d\n", ids[i]);
+    score += size[ids[i]];
+    sortie.push_back(ids[i]);
+    for(unsigned int j = 0; j < G[ids[i]].size(); j++){
+//    printf("j'exclus %d\n", G[ids[i]][j]);
+      taken[G[ids[i]][j]]=true;
+    }
+  }
+  return score;
+}
 
 int main(){
   scanf("%d",&n);
@@ -48,26 +70,22 @@ int main(){
   }
   }
   
-  vector<int> ids(G.size());
+  vector<bool> taken(G.size(),false);
+  vector<int> sortie;
+  ids.resize(G.size());
   for (unsigned i = 0; i < G.size(); i++) {
   ids[i]=i;
   }
-  
   sort(ids.begin(),ids.end(),compare_vect);
-   
-  vector<bool> taken(G.size(),false);
-  vector<int> sortie;
-   
-  for(unsigned int i=0;i<G.size();i++){
-    if(taken[ids[i]])continue;
-    printf("je prends %d\n", ids[i]);
-    sortie.push_back(ids[i]);
-    for(unsigned int j = 0; j < G[ids[i]].size(); j++){
-    printf("j'exclus %d\n", G[ids[i]][j]);
-      taken[G[ids[i]][j]]=true;
-    }
-  }
-  
+
+  int score = optimize(taken, sortie);
+
+  printf("SCORE %d\n", score);
+
+//  while (true) {
+//
+//  }
+
   // output
   printf("%d\n", (int) sortie.size());
   for (unsigned i = 0; i < sortie.size(); i++) {