제출 #706697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
706697		dachef	버섯 세기 (IOI20_mushrooms)	C++14	0 / 100	2 ms	208 KiB

mushrooms

#include <iostream>
#include <bits/stdc++.h>
#include "mushrooms.h"
#include <vector>
using namespace std;

int a[20000];
int ac = 1;
int b[20000];
int bc = 0;
int p = 1;  //Pointer
int co;
int ng;


int c = 0;
int temp;


void printSpez(){
  cout << " a: ";
    for(int i = 0; i < ac; i++){
      cout  << a[i] << " ";
    }
    cout << endl;
    cout <<" b: ";
    for(int i = 0; i < bc; i++){
      cout  << b[i] << " ";
    }
    cout << endl;
  return;
}

bool singleTry(){
  if(use_machine({a[0],p}) == 1){
    b[bc] = p;
    p++; bc++; co--;
    return false;
  } else {
    a[ac] = p;
    p++; ac++;
    return true;
  }
}

void get2Expl(bool x){
  if(p+1==ng){
    singleTry();
    return;
  }else if(p+1>=ng)
    return;
  if(x){
    temp = use_machine({a[0],p,a[1],p+1});
    if(temp == 3){
      b[bc] = p; b[bc+1] = p+1;
      p+=2; bc+=2; co-=2;
    } else if(temp == 2){
      b[bc] = p; a[ac] = p+1;
      p+=2; bc++; ac++; co--;
    } else if(temp == 1){
      a[ac] = p; b[bc] = p+1;
      p+=2; bc++; ac++; co--;
    } else if(temp == 0){
      a[ac] = p; a[ac+1] = p+1;
      p+=2; ac+=2;
    }
  } else {
    temp = use_machine({b[0],p,b[1],p+1});
    if(temp == 3){
      a[ac] = p; a[ac+1] = p+1;
      p+=2; ac+=2;
    } else if(temp == 2){
      a[ac] = p; b[bc] = p+1;
      p+=2; bc++; ac++; co--;
    } else if(temp == 1){
      b[bc] = p; a[ac] = p+1;
      p+=2; bc++; ac++; co--;
    } else if(temp == 0){
      b[bc] = p; b[bc+1] = p+1;
      p+=2; bc+=2; co-=2;
    }
  } 
}

void getMax(bool x){
  int temp;
  vector<int> v;
  c = 0;
  
cout << "ac: " << ac << "   bc: " << bc<< endl;
  if(x){
    
    for(int i = 0; i < ac && i < ng-p; i++){
      v.push_back(a[i]);
      v.push_back(p+i);
      cout << a[i] << " " << (p+i) << " ";
      c++;
    }
    cout << endl;
  } else {
    for(int i = 0; i < bc && i < ng-p; i++){
      
      v.push_back(b[i]);
      v.push_back(p+i);
      cout << b[i] << " " << (p+i) << " ";
      c++;
    }
    cout << endl;
  }
  //pointer wird nicht genung verschoben -> Duplicate Value 
  //1 7 2 8 4 9 5 10 
  //1 11 2 12 4 13 5 14 11 15 
  temp = use_machine(v);
  if(x){
    if(temp%2 == 0){
      a[ac] = p + c - 1;
      ac++; 
    } else {
      b[bc] = p + c - 1;
      bc++; temp += 2;
    }
    cout << "c: "<< c << "   hits: " << (temp) << endl;
    co -= (temp/2);

  } else {
    if(temp%2 == 1){
      a[ac] = p + c - 1;
      ac++; temp+=2;
    } else {
      b[bc] = p + c - 1;
      bc++; 
    }
    cout << "c: "<< c << "   hits: " << (temp) << endl;
    co -= c - (temp/2);   
  
  }
  p+=c;
}

void bomb(bool x){
  // vector<int> v1;
  // vector<int> v2;
  // vector<int> v3;
  if(p+6>=ng)
    return;
  int temp;
  int sum = 0;
  bool nskip = true;
  c = 0;   
  

  if(x){
    //AAAAAAAAAAAAAAAAAAAA
    // v1.push_back(a[0]);
    // v1.push_back(p);
    // v1.push_back(a[1]);
    // v1.push_back(p+1);
    // v1.push_back(a[2]);
    // v1.push_back(p+2);
    // v1.push_back(a[3]);
    // v1.push_back(p+4);
    cout << "1. " << p << " " << p+1 << " " << p+2 << "    " << p+4<<endl;
    temp = use_machine({a[0], p, a[1], p+1, a[2], p+2, a[3], p+4});
    sum += 16 * (int)(temp / 2);

    if(temp%2 == 0){
      a[ac] = p + 4;
      ac++; 
    } else {
      b[bc] = p + 4;
      bc++; co--;
    }

    // v2.push_back(a[0]);
    // v2.push_back(p+2);
    // v2.push_back(a[1]);
    // v2.push_back(p+3);
    // v2.push_back(a[2]);
    // v2.push_back(p+5);
    cout << "2. " << p+2 << " " << p+3 << "    " << p+5<<endl;
    temp = use_machine({a[0], p+2, a[1], p+3, a[2], p+5});
    sum += 4 * (int)(temp / 2);

    if(temp%2 == 0){
      a[ac] = p + 5;
      ac++; 
    } else {
      b[bc] = p + 5;
      bc++; co--;
    }
    switch(sum) {
      case 0: temp = 0; nskip = false; sum = 0; break;
      case 32: temp = 3; nskip = false; sum = 33; break;
      case 52: temp = 7; nskip = false; sum = 53; break;
      case 4: temp = 8; nskip = false; sum = 5; break;
      case 24: temp = 12; nskip = false; sum = 25; break;
      case 56: temp = 15; nskip = false; sum = 58; break;
      default: break;
    } 


    
    if(nskip){
    // v3.push_back(a[0]);
    // v3.push_back(p+1);
    // v3.push_back(a[1]);
    // v3.push_back(p+3);
    // v3.push_back(a[2]);
    // v3.push_back(p+6);
    cout << "3. " << p+1 << " " << p+3 << "    " << p+6<<endl;
    temp = use_machine({a[0], p+1, a[1], p+3, a[2], p+6});
    sum += 1 * (int)(temp / 2);

    if(temp%2 == 0){
      a[ac] = p + 6;
      ac++; 
    } else {
      b[bc] = p + 6;
      bc++; co--;
    }
    }
  }else {
  // //BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

    // v1.push_back(b[0]);
    // v1.push_back(p);
    // v1.push_back(b[1]);
    // v1.push_back(p+1);
    // v1.push_back(b[2]);
    // v1.push_back(p+2);
    // v1.push_back(b[3]);
    // v1.push_back(p+4);
    cout << endl << "1b" << endl;
    cout << endl << b[0] << " " << p << " " << b[1] << " " << p+1 << " ";
    cout << b[2] << " " << p+2 << " " << b[3] << " " << p+4 << endl;
    temp = use_machine({b[0], p, b[1], p+1, b[2], p+2, b[3], p+4});
    sum += 16 * (3-(int)(temp / 2));

    if(temp%2 == 1){
      a[ac] = p + 4;
      ac++; 
    } else {
      b[bc] = p + 4;
      bc++; co--;
    }

    // v2.push_back(b[0]);
    // v2.push_back(p+2);
    // v2.push_back(b[1]);
    // v2.push_back(p+3);
    // v2.push_back(b[2]);
    // v2.push_back(p+5);
    cout << endl << "2b" << endl;
    temp = use_machine({b[0], p+2, b[1], p+3, b[2], p+5});
    sum += 4 * (2 - (int)(temp / 2));

    if(temp%2 == 1){
      a[ac] = p + 5;
      ac++; 
    } else {
      b[bc] = p + 5;
      bc++; co--;
    }
    
    
    switch(sum) {
      case 0: temp = 0; nskip = false; sum = 0; break;
      case 32: temp = 3; nskip = false; sum = 33; break;
      case 52: temp = 7; nskip = false; sum = 53; break;
      case 4: temp = 8; nskip = false; sum = 5; break;
      case 24: temp = 12; nskip = false; sum = 25; break;
      case 56: temp = 15; nskip = false; sum = 58; break;
      default: break;
    }


    
    if(nskip){
    // v3.push_back(b[0]);
    // v3.push_back(p+1);
    // v3.push_back(b[1]);
    // v3.push_back(p+3);
    // v3.push_back(b[2]);
    // v3.push_back(p+6);
    cout << endl << "3b" << endl;
    temp = use_machine({b[0], p+1, b[1], p+3, b[2], p+6});
    sum += 1 * (2 - (int)(temp / 2));

    if(temp%2 == 1){
      a[ac] = p + 6;
      ac++; 
    } else {
      b[bc] = p + 6;
      bc++; co--;
    }

    }
  

  }
    
    cout << endl << sum << endl;
    switch(sum) {
      case 0: temp = 0; break;
      case 16: temp = 1; break;
      case 17: temp = 2; break;
      case 33: temp = 3; break;
      case 20: temp = 4; break;
      case 36: temp = 5; break;
      case 37: temp = 6; break;
      case 53: temp = 7; break;
      case 5: temp = 8; break;
      case 21: temp = 9; break;
      case 22: temp = 10; break;
      case 38: temp = 11; break;
      case 25: temp = 12; break;
      case 41: temp = 13; break;  
      case 42: temp = 14; break;
      case 58: temp = 15; break;
      default: temp = 0; break;
    }
    printSpez();

  
      for(int i = 3; i >= 0; i--){
        if(temp%2 == 0){
          a[ac] = p + 3-i;
          ac++; 
        } else {
          b[bc] = p + 3-i;
          bc++; co--;
        }
        temp /= 2;
      }
  printSpez();
  if(nskip)
    p += 7;
  else
    p += 6;

///Achtung
  //}
  ///Achtung
    
    return;
}

int stupid(int n){
    int cr = n;
  for(int i = 1; i < n-1; i+=2)
    cr -= use_machine({i,0,i+1});
  if(n%2==0)
    cr -= use_machine({0,n-1});
  return cr;
}




int count_mushrooms(int n){
  co = n;
  ng = n;
  a[0] = 0;

  if(n < 449){   //450 möglich normalerweise 400
    return stupid(n);
  }
  
  
  if(!singleTry())
    singleTry();

  
  // for(int i = 0; i < 85; i++){
  //   get2Expl(ac>bc);
  // }

  while(ac<4 && bc<4)
    get2Expl(ac>bc);

  
  for(int i = 0; i < 25; i++){
    bomb(ac>bc);
  }

  
//   cout << endl << ac <<endl;
// for(int i = 0; i < ac; i++){
//     cout << a[i] << " ";
//   }
// cout << endl;
//     cout << bc <<endl;
// for(int i = 0; i < bc; i++){
//     cout << b[i] << " ";
//   }
// cout << endl << endl;
  while(p<n){                                  //kritisch
    getMax(ac>bc);
  cout << ng-co << endl;
//       cout << endl << ac <<endl;
// for(int i = 0; i < ac; i++){
//     cout << a[i] << " ";
//   }
// cout << endl;
//     cout << bc <<endl;
// for(int i = 0; i < bc; i++){
//     cout << b[i] << " ";
//   }
// cout << endl << endl;
 }
  return co;
}

// 34
// 0 0 0 1 0 0 1 0 1 0  1 0 1 1 0 1 0  1 0 1 1 1 0 0 1  1 0 0 1 1 1 1 1  1

• Subtask 1: 0 / 100