Advertisement
Guest User

Untitled

a guest
Mar 31st, 2020
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.32 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <list>
  5. #include <random>
  6. #include <algorithm>
  7. #include <thread>
  8. #include <assert.h>
  9. #include <cstring>
  10.  
  11. using namespace std;
  12.  
  13. typedef long long int lint;
  14. typedef vector<lint> ivector;
  15.  
  16.  
  17. void printvector(ivector nums){
  18.     for_each(nums.begin(),nums.end(),[](lint value){printf("%lld ",value);});
  19.     printf("\n");  
  20. }
  21.  
  22. //max 100 elemre
  23. class Solver{
  24. public:
  25.     //Numbersnek legalább 2*n-1 memória területtel rendelkeznie kell
  26.     Solver(lint *numbers, lint n):numbers(numbers),n(n){
  27.         zeroSumResult = new bool[2*n-1]; //Ebben tároljuk, hogy mit választottunk be és mit nem
  28.         choosed = new lint[n];
  29.         memset(zeroSumResult,0,sizeof(bool)*2*n-1);
  30.     }
  31.  
  32.     ~Solver(){
  33.         //delete[] choosed; nem érdekel most a leak...
  34.         //delete[] zeroSumResult;
  35.     }
  36.  
  37.     bool *zeroSumResult;
  38.  
  39.     void solve(){
  40.         srand(time(0));
  41.         bool solved = false;
  42.        
  43.         unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
  44.         std::default_random_engine e(seed);
  45.  
  46.         while(!solved){
  47.             std::shuffle(numbers,numbers+(2*n-1),e); //Feltesszük, hogy numbers mérete mindig 2*n - 1
  48.             max_step = 300;
  49.             step = 0;
  50.             choosedSize = 0;
  51.  
  52.             solved = chooseElementsUtil(0);
  53.             if(solved){
  54.                 break;
  55.             }
  56.         }
  57.     }
  58.  
  59. private:
  60.     lint *numbers;
  61.     const lint n;
  62.    
  63.     lint *choosed;
  64.     int choosedSize;
  65.  
  66.  
  67.     int step = 0;
  68.     int max_step = 400;
  69.  
  70.     bool chooseElementsUtil(lint index){
  71.         step++;
  72.         if(step>max_step)return false; // 800 volt fixen eredetileg
  73.  
  74.         if(choosedSize == n){
  75.             lint sum = 0;
  76.             for(int i =0;i<choosedSize;i++){
  77.                 sum += numbers[choosed[i]];
  78.                 sum = sum%n;
  79.             }
  80.  
  81.             if(sum%n == 0){
  82.                 for(int i =0;i<choosedSize;i++){
  83.                     zeroSumResult[choosed[i]] = true;
  84.                 }
  85.             }
  86.             return sum%n == 0;
  87.         }
  88.  
  89.         //nem tudunk többet kiválasztani
  90.         if(index == 2*n-1){
  91.             return false;
  92.         }
  93.  
  94.         //A jelenlegi beletehetjük
  95.  
  96.         choosed[choosedSize++] = index;
  97.         bool ok1 = chooseElementsUtil(index+1);
  98.         choosedSize--;
  99.  
  100.         if(ok1)return true;
  101.  
  102.         //vagy nem tesszük
  103.         bool ok2 = chooseElementsUtil(index+1);
  104.        
  105.         return ok2;
  106.     }
  107. };
  108.  
  109.  
  110. #define THREAD_COUNT 10
  111.  
  112.  
  113. void testZeroSumChooser(){
  114.     auto start = std::chrono::system_clock::now();
  115.  
  116.     for(int tst = 0;tst<10000;tst++){
  117.         //printf("\nRUN NEW TEST ☢️\n");
  118.         int random_n = 100;//(rand() % 100)+2; //minimum 2 szám
  119.         int numbers_count = random_n*2 -1; //2n-1, Erdős
  120.         //printf("n: %d, 2n-1: %d\n",random_n,numbers_count);
  121.  
  122.         lint numbers[numbers_count];
  123.         for(int i =0;i<numbers_count;i++)numbers[i] = rand()%10;
  124.        
  125.         //printf("input numbers: \n");
  126.         //printvector(nums);
  127.  
  128.         Solver solver(numbers,random_n);
  129.         solver.solve();
  130.  
  131.         //check sum
  132.         lint s = 0;
  133.  
  134.         //printf("Választott: ");
  135.         for(int i =0;i<numbers_count;i++){
  136.             if(solver.zeroSumResult[i]){
  137.                 s += numbers[i];
  138.             }
  139.         }
  140.  
  141.         //printf("\n");
  142.         assert(s%random_n == 0);
  143.         //printf("SUM OK 🎈");
  144.     }
  145.  
  146.     auto end = std::chrono::system_clock::now()-start;
  147.     //printf("\nTiming: %dms\n",std::chrono::duration_cast<std::chrono::milliseconds>(end).count());
  148. }
  149.  
  150.  
  151. #define MAX_NUMBERS 100*100*100*2
  152. lint A,B,C;
  153. lint INPUT[MAX_NUMBERS*5];
  154.  
  155. void readInput(){
  156.     scanf("%lld %lld %lld",&A,&B,&C);
  157.     lint tmp;
  158.     for(int i =0;i<2*A*B*C;i++){
  159.         scanf("%lld", INPUT+i);
  160.     }
  161. }
  162.  
  163.  
  164. struct Ai{
  165.     lint factor; //sum(numbers)/a
  166.     vector<lint> numbers;
  167. };
  168.  
  169.  
  170. struct Bi{
  171.     lint factor;
  172.     vector<lint> AiFactors;
  173. };
  174.  
  175.  
  176. #include <map>
  177. void real_solver(){
  178.     int bcminus1 = B*C-1;
  179.    
  180.     int round = 2*B*C - 1;
  181.    
  182.     int inputsize = 2*A*B*C-1;
  183.     vector<Ai> ai;
  184.     ai.reserve(2*B*C-1);
  185.  
  186.     for(int i =0;i<round;i++){
  187.         int abs_start = i*(2*A - 1);
  188.         Solver solve(INPUT+abs_start,A);
  189.         solve.solve();
  190.  
  191.         Ai newai;
  192.         lint sum = 0;
  193.         for(int i =0;i<(2*A-1);i++){
  194.             int realindex = abs_start+i;
  195.            
  196.             if(solve.zeroSumResult[i] == true){
  197.                 newai.numbers.push_back(INPUT[realindex]);
  198.                 sum += INPUT[realindex];
  199.             }else{
  200.                 INPUT[inputsize++] = INPUT[realindex];
  201.             }
  202.         }
  203.         newai.factor = sum/A;
  204.         ai.push_back(newai);
  205.     }
  206.  
  207.    
  208.  
  209.     lint *aifactors = new lint[(2*B*C - 1) *3];
  210.  
  211.     for(int i =0;i<ai.size();i++)aifactors[i] = ai[i].factor;
  212.  
  213.     int round2 = 2*C-1; //ennyi új faktort kell kapnunk
  214.  
  215.  
  216.     int aifactorsize = (2*B*C - 1);
  217.     vector<Bi> bi;
  218.     bi.reserve(2*C-1);
  219.  
  220.     for(int i =0;i<round2;i++){
  221.         //printf("new round2:\n");
  222.  
  223.         int abs_start = i*(2*B - 1); // (2*B-1 elemenként processelünk)
  224.         Solver solve(aifactors+abs_start,B);
  225.         solve.solve();
  226.  
  227.         Bi newbi;
  228.         lint sum = 0;
  229.         for(int i =0;i<(2*B-1);i++){
  230.             int realindex = abs_start+i;
  231.            
  232.             //itt lesz olyan b, amibe nem választottunk B darabot
  233.             if(solve.zeroSumResult[i] == true){ //használta, tehát bekerül az Ai-ba
  234.                 newbi.AiFactors.push_back(aifactors[realindex]);
  235.                 sum += aifactors[realindex];
  236.             }else{
  237.                 aifactors[aifactorsize++] = aifactors[realindex];
  238.             }
  239.         }
  240.         //printf("newbi.factor = sum:%d/B:%d = %d, osztható amúgy? %d",sum,B,sum/B, sum%B == 0);
  241.         newbi.factor = sum/B;
  242.         bi.push_back(newbi);
  243.     }
  244.  
  245.     lint *bifactors = new lint[ (2*C-1)*3];
  246.  
  247.     for(int i =0;i<bi.size();i++){
  248.         bifactors[i] = bi[i].factor;
  249.     }
  250.  
  251.     Solver lastSolver(bifactors,C);
  252.     lastSolver.solve();
  253.     std::map<lint,lint> bichoosed; // key,pair -> milyenbifaktorból, mennyit
  254.  
  255.     int choosedc = 0;
  256.     for(int i =0;i<2*C-1;i++){
  257.         if(lastSolver.zeroSumResult[i] == true){
  258.             lint b = bifactors[i];
  259.             bichoosed[b]++;
  260.             choosedc++;
  261.         }
  262.     }
  263.  
  264.  
  265.     //most iterálunk a bifaktoron
  266.     std::map<lint,lint> aichoosed; //milyen ai-kat választottunk és mennyit
  267.  
  268.     for(Bi b : bi){
  269.         if(bichoosed[b.factor]>0){
  270.             for(lint aifac : b.AiFactors){
  271.                 aichoosed[aifac]++;
  272.             }
  273.             bichoosed[b.factor]--; //csökkentsük egyel
  274.         }
  275.     }
  276.  
  277.  
  278.     //A végén pedig csak az ai faktort kell iterálni egyszer és done
  279.     lint endsum = 0;
  280.     lint numbercount = 0;
  281.  
  282.     for(Ai a : ai){
  283.         if(aichoosed[a.factor]>0){
  284.             //kiírjuk ami benne van
  285.             for(lint num : a.numbers){
  286.                 numbercount++;
  287.                 printf("%lld ",num);
  288.                 endsum += num;
  289.             }
  290.             aichoosed[a.factor]--;
  291.         }
  292.     }
  293.  
  294. }
  295.  
  296.  
  297.  
  298. int main(){    
  299.     std::ios_base::sync_with_stdio(false);
  300.     std::cin.tie(0);
  301.  
  302.     readInput();
  303.     real_solver();
  304.  
  305.    
  306.     return 0;
  307. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement