Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- #include <list>
- #include <random>
- #include <algorithm>
- #include <thread>
- #include <assert.h>
- #include <cstring>
- using namespace std;
- typedef long long int lint;
- typedef vector<lint> ivector;
- void printvector(ivector nums){
- for_each(nums.begin(),nums.end(),[](lint value){printf("%lld ",value);});
- printf("\n");
- }
- //max 100 elemre
- class Solver{
- public:
- //Numbersnek legalább 2*n-1 memória területtel rendelkeznie kell
- Solver(lint *numbers, lint n):numbers(numbers),n(n){
- zeroSumResult = new bool[2*n-1]; //Ebben tároljuk, hogy mit választottunk be és mit nem
- choosed = new lint[n];
- memset(zeroSumResult,0,sizeof(bool)*2*n-1);
- }
- ~Solver(){
- //delete[] choosed; nem érdekel most a leak...
- //delete[] zeroSumResult;
- }
- bool *zeroSumResult;
- void solve(){
- srand(time(0));
- bool solved = false;
- unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
- std::default_random_engine e(seed);
- while(!solved){
- std::shuffle(numbers,numbers+(2*n-1),e); //Feltesszük, hogy numbers mérete mindig 2*n - 1
- max_step = 300;
- step = 0;
- choosedSize = 0;
- solved = chooseElementsUtil(0);
- if(solved){
- break;
- }
- }
- }
- private:
- lint *numbers;
- const lint n;
- lint *choosed;
- int choosedSize;
- int step = 0;
- int max_step = 400;
- bool chooseElementsUtil(lint index){
- step++;
- if(step>max_step)return false; // 800 volt fixen eredetileg
- if(choosedSize == n){
- lint sum = 0;
- for(int i =0;i<choosedSize;i++){
- sum += numbers[choosed[i]];
- sum = sum%n;
- }
- if(sum%n == 0){
- for(int i =0;i<choosedSize;i++){
- zeroSumResult[choosed[i]] = true;
- }
- }
- return sum%n == 0;
- }
- //nem tudunk többet kiválasztani
- if(index == 2*n-1){
- return false;
- }
- //A jelenlegi beletehetjük
- choosed[choosedSize++] = index;
- bool ok1 = chooseElementsUtil(index+1);
- choosedSize--;
- if(ok1)return true;
- //vagy nem tesszük
- bool ok2 = chooseElementsUtil(index+1);
- return ok2;
- }
- };
- #define THREAD_COUNT 10
- void testZeroSumChooser(){
- auto start = std::chrono::system_clock::now();
- for(int tst = 0;tst<10000;tst++){
- //printf("\nRUN NEW TEST ☢️\n");
- int random_n = 100;//(rand() % 100)+2; //minimum 2 szám
- int numbers_count = random_n*2 -1; //2n-1, Erdős
- //printf("n: %d, 2n-1: %d\n",random_n,numbers_count);
- lint numbers[numbers_count];
- for(int i =0;i<numbers_count;i++)numbers[i] = rand()%10;
- //printf("input numbers: \n");
- //printvector(nums);
- Solver solver(numbers,random_n);
- solver.solve();
- //check sum
- lint s = 0;
- //printf("Választott: ");
- for(int i =0;i<numbers_count;i++){
- if(solver.zeroSumResult[i]){
- s += numbers[i];
- }
- }
- //printf("\n");
- assert(s%random_n == 0);
- //printf("SUM OK 🎈");
- }
- auto end = std::chrono::system_clock::now()-start;
- //printf("\nTiming: %dms\n",std::chrono::duration_cast<std::chrono::milliseconds>(end).count());
- }
- #define MAX_NUMBERS 100*100*100*2
- lint A,B,C;
- lint INPUT[MAX_NUMBERS*5];
- void readInput(){
- scanf("%lld %lld %lld",&A,&B,&C);
- lint tmp;
- for(int i =0;i<2*A*B*C;i++){
- scanf("%lld", INPUT+i);
- }
- }
- struct Ai{
- lint factor; //sum(numbers)/a
- vector<lint> numbers;
- };
- struct Bi{
- lint factor;
- vector<lint> AiFactors;
- };
- #include <map>
- void real_solver(){
- int bcminus1 = B*C-1;
- int round = 2*B*C - 1;
- int inputsize = 2*A*B*C-1;
- vector<Ai> ai;
- ai.reserve(2*B*C-1);
- for(int i =0;i<round;i++){
- int abs_start = i*(2*A - 1);
- Solver solve(INPUT+abs_start,A);
- solve.solve();
- Ai newai;
- lint sum = 0;
- for(int i =0;i<(2*A-1);i++){
- int realindex = abs_start+i;
- if(solve.zeroSumResult[i] == true){
- newai.numbers.push_back(INPUT[realindex]);
- sum += INPUT[realindex];
- }else{
- INPUT[inputsize++] = INPUT[realindex];
- }
- }
- newai.factor = sum/A;
- ai.push_back(newai);
- }
- lint *aifactors = new lint[(2*B*C - 1) *3];
- for(int i =0;i<ai.size();i++)aifactors[i] = ai[i].factor;
- int round2 = 2*C-1; //ennyi új faktort kell kapnunk
- int aifactorsize = (2*B*C - 1);
- vector<Bi> bi;
- bi.reserve(2*C-1);
- for(int i =0;i<round2;i++){
- //printf("new round2:\n");
- int abs_start = i*(2*B - 1); // (2*B-1 elemenként processelünk)
- Solver solve(aifactors+abs_start,B);
- solve.solve();
- Bi newbi;
- lint sum = 0;
- for(int i =0;i<(2*B-1);i++){
- int realindex = abs_start+i;
- //itt lesz olyan b, amibe nem választottunk B darabot
- if(solve.zeroSumResult[i] == true){ //használta, tehát bekerül az Ai-ba
- newbi.AiFactors.push_back(aifactors[realindex]);
- sum += aifactors[realindex];
- }else{
- aifactors[aifactorsize++] = aifactors[realindex];
- }
- }
- //printf("newbi.factor = sum:%d/B:%d = %d, osztható amúgy? %d",sum,B,sum/B, sum%B == 0);
- newbi.factor = sum/B;
- bi.push_back(newbi);
- }
- lint *bifactors = new lint[ (2*C-1)*3];
- for(int i =0;i<bi.size();i++){
- bifactors[i] = bi[i].factor;
- }
- Solver lastSolver(bifactors,C);
- lastSolver.solve();
- std::map<lint,lint> bichoosed; // key,pair -> milyenbifaktorból, mennyit
- int choosedc = 0;
- for(int i =0;i<2*C-1;i++){
- if(lastSolver.zeroSumResult[i] == true){
- lint b = bifactors[i];
- bichoosed[b]++;
- choosedc++;
- }
- }
- //most iterálunk a bifaktoron
- std::map<lint,lint> aichoosed; //milyen ai-kat választottunk és mennyit
- for(Bi b : bi){
- if(bichoosed[b.factor]>0){
- for(lint aifac : b.AiFactors){
- aichoosed[aifac]++;
- }
- bichoosed[b.factor]--; //csökkentsük egyel
- }
- }
- //A végén pedig csak az ai faktort kell iterálni egyszer és done
- lint endsum = 0;
- lint numbercount = 0;
- for(Ai a : ai){
- if(aichoosed[a.factor]>0){
- //kiírjuk ami benne van
- for(lint num : a.numbers){
- numbercount++;
- printf("%lld ",num);
- endsum += num;
- }
- aichoosed[a.factor]--;
- }
- }
- }
- int main(){
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(0);
- readInput();
- real_solver();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement