fork download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <stdio.h>
  5.  
  6. using namespace std;
  7.  
  8. int bh[102];
  9. int use_bh[102];
  10. int sub_bh[102];
  11. int wsub_bh[102];
  12.  
  13. int all_bh_used()
  14. {
  15.     int i=0;
  16.     for(i=0;i<101;i++)
  17.     {
  18.         if(bh[i] > 0)return 0;
  19.     }
  20.     return 1;
  21. }
  22.  
  23. vector <vector <int> > match2(int height, int position, vector <vector <int> >  vl)
  24. {   
  25.  
  26.     if(bh[height+1] > 0)
  27.     {
  28.         vl[position-1].push_back(height+1);
  29.     }
  30.     if(bh[height] > 0)
  31.     {
  32.         vl[position-1].push_back(height);
  33.     }
  34.  
  35. 	return vl;
  36. }
  37.  
  38. int find(int depth, int ph, int p)
  39. {
  40.     int i;
  41.     if(use_bh[p] > 1)
  42.     {
  43.         for(i=depth;i<=ph+1;i++)
  44.         {
  45.             if(bh[i] > 0)
  46.             {            
  47.                 bh[i] -= 1;
  48.                 //cout<<"bh["<<i<<"]="<<bh[i]<<endl;
  49.                 sub_bh[i] += 1;
  50.                 return 1;            
  51.             }
  52.         }
  53.     }
  54.     else
  55.     {
  56.         if(bh[p] > 0)
  57.         {
  58.             bh[p] -= 1;
  59.             sub_bh[p] += 1;
  60.             return 1;
  61.         }
  62.     }
  63.     return 0;
  64. }
  65.  
  66. class CrossingTheRiver{
  67. 	public:
  68. 	CrossingTheRiver(){}
  69. 	~CrossingTheRiver(){}
  70. 	string isItEvenPossible(int waterWidth, int landWidth, vector<int>  blockHeight, int depth);
  71. };
  72.  
  73. string CrossingTheRiver::isItEvenPossible(int waterWidth, int landWidth, vector<int>  blockHeight, int depth)
  74. {
  75. 	string st;
  76. 	vector<vector <int> > vl;
  77.  
  78. 	int i=0, s, skip=0;
  79. 	int position = 1, ph=0, f=0, land_sum=0, old_ph=0, end_ph=0, f1=0, f2=0;
  80. 	int len_block = blockHeight.size();
  81.  
  82. 	for (int i = 0; i < waterWidth + landWidth; i++) {
  83.     	vector<int> row; 
  84.     	vl.push_back(row); 
  85. 	}
  86.  
  87.     //ini bh
  88.     for(i=0; i<102; i++)
  89.     {
  90.         bh[i] = 0;
  91.         use_bh[i] = 0;
  92.     }
  93.  
  94.     for(i=0;i<len_block;i++)
  95.     {
  96.         bh[blockHeight[i]] += 1;
  97.     }
  98.  
  99. 	while(position <= waterWidth + landWidth && 0 == f)
  100. 	{
  101. 		skip = 0;
  102.  
  103.         if(1 == all_bh_used())
  104.         {
  105.             f = 1;
  106.             break;
  107.         }
  108.  
  109.  
  110. 		if(position <= waterWidth)
  111. 		{
  112. 			ph += depth;
  113. 			vl = match2(ph, position, vl);
  114. 			if(vl[position-1].size() > 0)
  115. 			{
  116.                 ph = vl[position-1].back() - depth;
  117.                 bh[vl[position-1].back()] -= 1;
  118.                 use_bh[vl[position-1].back()] += 1;
  119.                 ++position;
  120. 			}
  121. 			else//vl[position-1].size() == 0
  122. 			{
  123. 				if(position > 1)
  124. 				{
  125. 					--position;
  126.                     s = vl[position-1].size();
  127.                     bh[vl[position-1][s-1]] += 1;
  128.                     use_bh[vl[position-1][s-1]] -= 1;
  129.                     vl[position-1].resize(s-1);
  130. 					if(s>1)
  131. 					{
  132.                         bh[vl[position-1].back()] -= 1;
  133.                         use_bh[vl[position-1].back()] += 1;
  134. 						ph = vl[position-1].back() - depth; 
  135. 						skip = 1;
  136.                         ++position;
  137. 					}
  138.  
  139. 					while(vl[position-1].size() == 0 && 0 == skip)
  140. 					{
  141.                         if(position > 1)
  142. 						{
  143. 							--position;
  144.                             s = vl[position-1].size();
  145. 							bh[vl[position-1][s-1]] += 1;
  146.                             use_bh[vl[position-1][s-1]] -= 1;
  147. 							vl[position-1].resize(s-1);
  148. 							if(s>1)
  149. 							{
  150. 								bh[vl[position-1].back()] -= 1;
  151.                                 use_bh[vl[position-1].back()] += 1;
  152. 								ph = vl[position-1].back() - depth; 
  153. 								++position;
  154. 								break;
  155. 							}
  156. 						}
  157. 						else
  158. 						{
  159. 							if(vl[position-1].size() > 0)
  160. 							{
  161.                                 s = vl[position-1].size();
  162.                                 bh[vl[position-1][s-1]] += 1;
  163.                                 use_bh[vl[position-1][s-1]] -= 1;
  164.                                 vl[position-1].resize(s-1);
  165.                                 if(s>1)
  166.                                 {
  167.                                     bh[vl[position-1].back()] -= 1;
  168.                                     use_bh[vl[position-1].back()] += 1;
  169.                                     ph = vl[position-1].back() - depth; 
  170.                                     ++position;
  171.                                     break;
  172.                                 }
  173. 							}
  174. 							else
  175. 							{
  176. 								f = 1;
  177. 								break;
  178. 							}
  179. 						}
  180. 					}
  181. 				}
  182. 				else//position == 1
  183. 				{
  184. 					if(vl[position-1].size() > 1)
  185. 					{
  186. 						s = vl[position-1].size();
  187. 						bh[vl[position-1][s-1]] += 1;
  188.                         use_bh[vl[position-1][s-1]] -= 1;
  189. 						vl[position-1].resize(s-1);
  190.                         if(s>1)
  191. 						{
  192. 							bh[vl[position-1].back()] -= 1;
  193.                             if(bh[vl[position-1].back()] < 0)cout<<"bh8["<<position<<"]="<<bh[vl[position-1].back()]<<endl;
  194.                             use_bh[vl[position-1].back()] += 1;
  195. 							ph = vl[position-1].back() - depth; 
  196. 							++position;
  197. 						}
  198. 					}
  199. 					else
  200. 					{
  201. 						f = 1;
  202. 						break;
  203. 					}
  204. 				}
  205. 			}	
  206. 		}
  207. 		else//position > waterWidth 
  208. 		{	
  209.             old_ph = ph;
  210.             land_sum = position - waterWidth - 1;
  211.             f1 = 0;
  212.             f2 = 0;
  213.             while(land_sum < landWidth)
  214.             {
  215.                 if(0 == bh[ph] && 0 == bh[ph+1])
  216.                 {
  217.                     if(use_bh[ph] > 0 && 0 == f1)
  218.                     {
  219.                         if(1 == find(depth, ph, ph))
  220.                         {
  221.                             land_sum += 1;
  222.                             use_bh[ph] -= 1;
  223.                             wsub_bh[ph] += 1;
  224.                         }
  225.                         else f1 = 1;
  226.                     }
  227.                     else if(use_bh[ph+1] > 0 && 0 == f2)
  228.                     {
  229.                         if(1 == find(depth, ph, ph+1))
  230.                         {
  231.                             land_sum += 1;
  232.                             use_bh[ph] -= 1;
  233.                             wsub_bh[ph] += 1;
  234.                             ++ph;
  235.                             f1 = 0;
  236.                             f2 = 0;
  237.                         }
  238.                         else f2 = 1;
  239.                     }
  240.                     else
  241.                     {
  242.                         end_ph = ph;
  243.                         break;
  244.                     }
  245.                 }
  246.                 else
  247.                 {
  248.                     if(bh[ph] > 0)
  249.                     {
  250.                         land_sum += bh[ph];
  251.                         sub_bh[ph] = bh[ph];
  252.                         bh[ph] = 0;
  253.                     }
  254.                     if(bh[ph+1] > 0)
  255.                     {
  256.                         land_sum += bh[ph+1];
  257.                         sub_bh[ph+1] = bh[ph+1];
  258.                         bh[ph+1] = 0;
  259.                         ++ph;
  260.                     }
  261.                 }
  262.             }
  263.  
  264.             for(i=depth;i<=end_ph;i++)
  265.             {
  266.                 if(sub_bh[i] > 0)
  267.                 {
  268.                     bh[i] += sub_bh[i];
  269.                     sub_bh[i] = 0;
  270.                 }
  271.                 if(wsub_bh[i] > 0)
  272.                 {
  273.                     use_bh[i] += wsub_bh[i];
  274.                     wsub_bh[i] = 0;
  275.                 }
  276.             }
  277.  
  278.             if(land_sum >= landWidth)
  279.             {
  280.                 position = waterWidth + landWidth + 1;
  281.                 break;
  282.             }
  283. 			else//vl[position-1].size() = 0
  284.             {
  285.  
  286. 				if(position > 1)
  287. 				{
  288. 					--position;
  289.  
  290. 					s = vl[position-1].size();
  291. 					bh[vl[position-1][s-1]] += 1;
  292.                     use_bh[vl[position-1][s-1]] -= 1;
  293. 					vl[position-1].resize(s-1);
  294.  
  295. 					if(s>1)
  296. 					{
  297. 						bh[vl[position-1].back()] -= 1;
  298.                         use_bh[vl[position-1].back()] += 1;
  299. 						if(position > waterWidth)
  300. 						{
  301. 							ph = vl[position-1].back();	
  302. 						}
  303. 						else
  304. 						{
  305. 							ph = vl[position-1].back() - depth;
  306. 						}
  307. 						++position;
  308. 						skip = 1;
  309. 					}
  310. 					while(vl[position-1].size() == 0 && 0==skip)
  311. 					{
  312. 						if(position > 1)
  313. 						{
  314. 							--position;
  315.  
  316.                             s = vl[position-1].size();
  317.                             bh[vl[position-1][s-1]] += 1;
  318.                             use_bh[vl[position-1][s-1]] -= 1;
  319.                             vl[position-1].resize(s-1);
  320.                             if(s>1)
  321. 							{
  322. 								bh[vl[position-1].back()] -= 1;
  323.                                 use_bh[vl[position-1].back()] += 1;
  324.                                 if(position > waterWidth)
  325. 								{
  326. 									ph = vl[position-1].back();	
  327. 								}
  328. 								else
  329. 								{
  330. 									ph = vl[position-1].back() - depth;
  331. 								}
  332. 								++position;
  333. 								break;
  334. 							}
  335. 						}
  336. 						else//while, position==1
  337. 						{
  338. 							if(vl[position-1].size() > 1)
  339. 							{
  340.  
  341.                                 s = vl[position-1].size();
  342. 								bh[vl[position-1][s-1]] += 1;
  343.                                 use_bh[vl[position-1][s-1]] -= 1;
  344. 								vl[position-1].resize(s-1);
  345. 								if(s>1)
  346. 								{
  347. 									bh[vl[position-1].back()] -= 1;
  348.                                     use_bh[vl[position-1].back()] += 1;
  349. 									if(position > waterWidth)
  350. 									{
  351. 										ph = vl[position-1].back();	
  352. 									}
  353. 									else
  354. 									{
  355. 										ph = vl[position-1].back() - depth;
  356. 									}
  357. 									++position;
  358. 									break;
  359. 								}
  360. 							}
  361. 							else
  362. 							{
  363. 								f = 1;
  364. 								break;
  365. 							}
  366. 						}
  367. 					}
  368. 				}
  369. 				else//if position == 1
  370. 				{
  371. 					if(vl[position-1].size() > 1)
  372. 					{
  373.                         s = vl[position-1].size();
  374.                         bh[vl[position-1][s-1]] += 1;
  375.                         use_bh[vl[position-1][s-1]] -= 1;
  376.                         vl[position-1].resize(s-1);
  377.  
  378.                         if(s>1)
  379. 						{
  380. 							bh[vl[position-1].back()] -= 1;
  381.                             use_bh[vl[position-1].back()] += 1;
  382. 							if(position > waterWidth)
  383. 							{
  384. 								ph = vl[position-1].back();	
  385. 							}
  386. 							else
  387. 							{
  388. 								ph = vl[position-1].back() - depth;
  389. 							}
  390. 							++position;
  391. 						}
  392. 					}
  393. 					else
  394. 					{
  395. 						f = 1;
  396. 						break;
  397. 					}
  398. 				}
  399. 			}
  400. 		}
  401. 	}
  402. 	if(0 == f)
  403.     {
  404.         st = "POSSIBLE";
  405.     }
  406. 	else {
  407. 		if (0 == ph)st = "POSSIBLE";
  408. 		else
  409. 		{
  410. 			st = "IMPOSSIBLE";	
  411. 		}
  412. 	}
  413.  
  414. 	return st;
  415. }
  416.  
  417.  
  418. int main()
  419. {
  420.     CrossingTheRiver cr;
  421.     /*
  422.     int myints[] = {
  423.         5, 9, 41, 7, 5, 7, 8, 3, 6, 16, 16, 81, 6, 6, 17, 5, 15, 5, 13, 5, 63, 10, 14, 5, 12, 69, 5, 6, 7, 9, 64, 14, 11, 4, 7, 3, 14, 7, 13, 96, 4, 92, 33, 97, 45, 4, 55, 7, 16, 7
  424.         };
  425.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  426.     cout<<cr.isItEvenPossible(13, 26, b, 2);
  427.     */
  428.     //Possible
  429.     /*
  430.     int myints[] = {
  431.         3,4,4,5,5, 6
  432.         };
  433.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  434.     cout<<cr.isItEvenPossible(3, 3, b, 2);
  435.     *///Possible
  436.     /*
  437.     int myints[] = {
  438.         3,4,4,5,6, 6
  439.         };
  440.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  441.     cout<<cr.isItEvenPossible(3, 3, b, 2);
  442.     */
  443.     //impossible
  444.     /*
  445.     int myints[] = {
  446.         2, 2, 60, 2, 5, 5, 2, 14, 89, 4, 11, 49, 83, 31, 61, 21, 62, 5, 3, 2, 6, 18, 2, 47, 5
  447.         };
  448.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  449.     cout<<cr.isItEvenPossible(11, 2, b, 2);
  450.     *///Possible
  451.     /*
  452.     int myints[] = {
  453.         19, 21, 13, 23, 17, 25, 22, 29, 14, 18, 29, 19, 20, 14, 25, 19, 27, 14, 21, 28, 15, 25, 17, 26, 25, 13, 20, 29, 13, 20, 16, 22, 20, 24, 16, 24, 13, 19, 24, 24, 14, 18, 16, 22, 21
  454.         };
  455.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  456.     cout<<cr.isItEvenPossible(35, 10, b, 13);
  457.     */
  458.     //Possible
  459.     /*
  460.     int myints[] = {
  461.         2, 3, 4, 5
  462.         };
  463.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  464.     cout<<cr.isItEvenPossible(3, 1, b, 2);
  465.     *///imposible
  466.  
  467.     int myints[] = {
  468.         14, 22, 13, 26, 28, 20, 24, 19, 13, 23, 21, 16, 27, 25, 14, 18, 27, 28, 20, 22, 16, 12, 29, 15, 12, 17, 21, 23, 13, 14, 18, 21, 18, 19, 17, 28
  469.         };
  470.     vector <int> b(myints, myints + sizeof(myints) / sizeof(int));
  471.     cout<<cr.isItEvenPossible(33, 4, b, 11);
  472.  
  473.     //imposible
  474.     //getchar();
  475.     return 0;
  476. }
Success #stdin #stdout 1.13s 2996KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/lf8KnL
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!