Advertisement
Guest User

Untitled

a guest
Nov 14th, 2018
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.58 KB | None | 0 0
  1. //Jakub Jakubowski
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. int n,x,j,najsuma=2000001,zero,suma,rozm,xx,ok;
  9.  
  10. bool da_sie(int tabli[][3],int xx,int nt)
  11. {
  12. for (int i=3;i<nt;++i)
  13. if (tabli[i][2]!=xx)
  14. if (tabli[i][2]!=-xx)
  15. return 0;
  16. return 1;
  17. }
  18.  
  19. int main()
  20. {
  21. ios_base::sync_with_stdio(0);
  22. cin.tie(0);
  23. vector <int> numerki;
  24. vector <int> dworzec (1000001,0);
  25. vector <int> lotnisko (1000001,0);
  26. cin >> n;
  27. int tab[n][3];
  28. if (n==3)
  29. {
  30. cin >> tab[0][0]>>tab[0][1];
  31. cout << "TAK"<<endl;
  32. cout << 1 << " "<< 2 << " "<< tab[0][0]<<endl;
  33. cout << 2 << " "<< 3 << " "<< tab[0][1];
  34. return 0;
  35. }
  36. vector <int> srodek ;
  37. vector <int> roznica;
  38. for (int i=2;i<n;++i)
  39. cin >> tab[i][0];
  40. for (int i=2;i<n;++i)
  41. {
  42. cin >> tab[i][1];
  43. tab[i][2]=tab[i][0]-tab[i][1];
  44. suma=tab[i][0]+tab[i][1];
  45. if (suma==najsuma)
  46. {srodek.push_back(tab[i][2]);numerki.push_back(i);}
  47. if (suma<najsuma)
  48. {
  49. srodek.clear();
  50. numerki.clear();
  51. najsuma=suma;
  52. srodek.push_back(tab[i][2]);
  53. numerki.push_back(i);
  54. }
  55.  
  56. if (tab[i][2]>0)
  57. if (dworzec[tab[i][2]]==0)
  58. {dworzec[tab[i][2]]=-1;
  59. roznica.push_back(tab[i][2]);}
  60. else if (tab[i][2]<0)
  61. if (lotnisko[-tab[i][2]]==0)
  62. {lotnisko[-tab[i][2]]=-1;
  63. roznica.push_back(tab[i][2]);}
  64. else
  65. {
  66. if (dworzec [0]==0)
  67. {
  68. {dworzec[0]=1;
  69. roznica.push_back(0);}
  70. }
  71. if (tab[i][1]<zero)
  72. zero=suma;
  73. }
  74. }
  75. xx=tab[2][2];
  76. rozm=srodek.size();
  77. if (xx!=0)
  78. if (da_sie(tab,xx,n)==1)
  79. {
  80. cout << "TAK"<<endl;
  81. cout << 1 << " "<< n << " " << xx<<endl;
  82. for (int i=2;i<n;++i)
  83. if (tab[i][2]>0)
  84. cout << i << " "<< n << " " << tab[i][1]<<endl;
  85. else
  86. cout << i << " "<< 1 << " " << tab[i][0]<<endl;
  87. return 0;
  88. }
  89. if (zero!=0)
  90. if (zero!=najsuma)
  91. {
  92. cout << "NIE";
  93. return 0;
  94. }
  95.  
  96. if (roznica.size()>rozm+2)
  97. {
  98. cout << "NIE";
  99. return 0;
  100. }
  101. dworzec[najsuma]=n;
  102. lotnisko[najsuma]=1;
  103. for (int i=0;i<rozm;++i)
  104. {
  105. if (srodek[i]>=0)
  106. dworzec[srodek[i]]=numerki[i];
  107. else
  108. lotnisko[-srodek[i]]=numerki[i];
  109.  
  110. }
  111. for (int i=0;i<roznica.size();++i)
  112. {
  113. if (roznica[i]>=0)
  114. {
  115. if (dworzec[roznica[i]]==-1)
  116. {
  117. cout << "NIE";
  118. return 0;
  119. }
  120. }
  121. else
  122. if (lotnisko[roznica[i]]==-1)
  123. {
  124. cout << "NIE";
  125. return 0;
  126. }
  127. }
  128.  
  129.  
  130. vector <int> a (rozm);
  131. vector <int> xd (1000001);
  132. for (int i=0;i<rozm;++i)
  133. if (srodek[i]>=0)
  134. {a[i] = tab[dworzec[srodek[i]]][0];
  135. xd[a[i]]=dworzec[srodek[i]];}
  136. else
  137. {a[i] = tab[lotnisko[-srodek[i]]][0];
  138. xd[a[i]]=lotnisko[-srodek[i]];}
  139. sort(a.begin(),a.end());
  140. for (int i=1;i<rozm;++i)
  141. if (a[i] - a[i-1]==0)
  142. {cout << "NIE";
  143. return 0;}
  144. cout << "TAK"<<endl;
  145. cout << 1 << " "<< xd[a[0]]<< " "<< a[0]<<endl;
  146. tab [xd[a[0]]][2] = -1;
  147. for (int i=1;i<rozm-1;++i)
  148. {
  149. cout << xd[a[i-1]] << " "<<xd[a[i]] << " " << a[i] - a[i-1]<<endl;
  150.  
  151. tab[xd[a[i]]][2]=-1;
  152. }
  153.  
  154. if (rozm>1)
  155. {cout << xd[a[rozm-2]] << " "<<xd[a[rozm-1]] << " " << a[rozm-1] - a[rozm-2]<<endl<<xd[a[rozm-1]]<< " "<<n<<" "<<tab[xd[a[rozm-1]]][1]<<endl;
  156. tab[xd[a[rozm-1]]][2]=-1;}
  157. else
  158. cout << xd[a[0]] << " "<< n << " "<<tab[xd[a[0]]][1]<<endl;
  159. for (int i=2;i<n;++i)
  160. {
  161. if (tab[i][2]!=-1)
  162. {
  163. if (tab[i][2]==najsuma)
  164. cout << n << " "<< i<< " " << tab[i][1]<<endl;
  165. else if (tab[i][2]==-najsuma)
  166. cout << 1 << " "<< i<< " " << tab[i][0]<<endl;
  167. else if (tab[i][2]>=0)
  168. {
  169. cout << dworzec[tab[i][2]] << " " << i << " " << tab[i][1] - tab[dworzec[tab[i][2]]][1]<<endl;
  170. }
  171. else
  172. {
  173. cout << lotnisko[-tab[i][2]] << " " << i << " " << tab[i][0] - tab[lotnisko[-tab[i][2]]][0]<<endl;
  174. }
  175.  
  176. }
  177. }
  178. return 0;
  179. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement