API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Oct 21st, 2018
77
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 12.72 KB | None | 0 0
raw download clone embed print report
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int x[]={0,1,0,-1};
  4. int y[]={1,0,-1,0};
  5. vector<int>ruchy;
  6. vector<long long>pozycje;
  7. long long dlugosc=-1;
  8. long long X,Y,cX,cY,nX,nY;
  9. long long xs,ys,n;
  10. long long wyst,t,wynik,teraz=-1;
  11. long long rodz=-1;
  12. bool ujem=true;
  13. int binsearch(long long szuk){
  14. // cout<<"szukam "<<t<<" wsrod \n";
  15. // for(auto it: pozycje) cout<<it<<" ";
  16. int p=0, k=pozycje.size()-1;
  17. int sr=(p+k)/2;
  18. while(k-p>1){
  19. sr=(p+k)/2;
  20. if(pozycje[sr]>szuk) k=sr;
  21. else p=sr;
  22. }
  23. // cout<<"\n znalazlem "<<p<<"\n";
  24. return p;
  25. }
  26.  
  27. void sprawdz(int rodz){
  28. //cout<<"bombi "<<rodz<<endl;
  29. // cout<<X<<" "<<nX<<" "<<Y<<" "<<nY<<endl;
  30. if(rodz==0 && nX == xs && ys > Y && ys <= nY){
  31. //cout<<"bong 1 \n";
  32. wyst++;
  33. pozycje.push_back(dlugosc+abs(Y-ys));
  34. }
  35. else if(rodz==1 && nY == ys && xs > X && xs <= nX){
  36. //cout<<"bong 2 \n";
  37. wyst++;
  38. pozycje.push_back(dlugosc+abs(X-xs));
  39. }
  40. else if(rodz==2 && nX == xs && ys < Y && ys >= nY){
  41. //cout<<"bong 3 \n";
  42. wyst++;
  43. long long pom=abs(Y-ys);
  44. pozycje.push_back(dlugosc+pom);
  45. }
  46. else if(rodz==3 && nY == ys && xs < X && xs >= nX){
  47. //cout<<"bong 4 \n";
  48. wyst++;
  49. pozycje.push_back(dlugosc+abs(X-xs));
  50. }
  51. }
  52. void sprawdzdla41(int rodz,int i){
  53. nY=Y+y[rodz]*ruchy[i];
  54. nX=X+x[rodz]*ruchy[i];
  55. if(rodz == 0 || rodz == 2){
  56. double m=((double)xs-(double)X)/(double)cX;
  57. if(m==(long long)m){
  58. //cout<<"wszedlem w m1 "<<m<<endl;
  59. if(rodz==0){
  60. //cout<<"wszedlem w 1 \n";
  61. if(Y + m*cY < ys && ys <= nY + m*cY ){
  62. // cout<<"chce dodac do wyniku \n";
  63. // cout<<"teraz "<<teraz<<endl;
  64. if(m==0 && t>=teraz+abs(Y-ys)) wynik++;
  65. else if(m>0 && t>= teraz + abs(Y+m*cY-ys) + m * (dlugosc+1)) wynik++;
  66. }
  67.  
  68. }
  69. if(rodz==2){
  70. // cout<<"wszedlem w 3 \n";
  71. if(Y + m*cY > ys && ys >= nY + m*cY ){
  72. // cout<<"chce dodac do wyniku \n";
  73. // cout<<"teraz "<<teraz<<endl;
  74. if(m==0 && t>=teraz+abs(Y-ys)) wynik++;
  75. else if(m>0 && t>= teraz + abs(Y+m*cY-ys) + m * (dlugosc+1)) wynik++;
  76. }
  77. }
  78. }
  79. }
  80. else if(rodz == 1 || rodz == 3){
  81. double m=((double)ys-(double)Y)/(double)cY;
  82. if(m==(long long)m){
  83. //cout<<"wszedlem w m2 "<<m<<endl;
  84. if(rodz==1){
  85. //cout<<"wszedlem w 2\n";
  86. //cout<<X<<" "<<nX<<endl;
  87. if(X + m*cX < xs && xs <= nX + m*cX ){
  88. // cout<<"chce dodac do wyniku \n";
  89. // cout<<"teraz "<<teraz<<endl;
  90. if(m==0 && t>=teraz+abs(X-xs)) wynik++;
  91. else if(m>0 && t>= teraz + abs(X+m*cX-xs) + m * (dlugosc+1)) wynik++;
  92. }
  93. }
  94.  
  95. if(rodz==3){
  96. // cout<<"wszedlem w 4\n";
  97. if(X + m*cX > xs && xs >= nX + m*cX ){
  98. // cout<<"chce dodac do wyniku \n";
  99. // cout<<"teraz "<<teraz<<endl;
  100. if(m==0 && t>=teraz+abs(X-xs)) wynik++;
  101. else if(m>0 && t>= teraz + abs((X+m*cX)-xs) + m * (dlugosc+1)) wynik++;
  102. }
  103. }
  104. }
  105. }
  106. //cout<<wynik<<endl;
  107. }
  108.  
  109. void sprawdzdla42(int rodz,int i){
  110. int starrodz=rodz;
  111. if(ujem==false){
  112. if(rodz==2) {
  113. rodz=0;
  114. }
  115. else if(rodz==0){
  116. rodz=2;
  117. }
  118. }
  119. nY=Y+y[rodz]*ruchy[i];
  120. nX=X+x[rodz]*ruchy[i];
  121.  
  122. if(rodz==0 && xs == X){
  123. double mmin=ceil(((double)ys-(double)nY)/(double)cY);
  124. // cout<<"mmin "<<mmin<<endl;
  125. if(mmin<0) mmin=0;
  126. if(t>=abs(Y-ys)+teraz){
  127. long long mmax;
  128. double mmaxi=((double)t+Y-teraz-ys)/(dlugosc+1ll-cY);
  129. if(abs((double)t - (mmaxi * ((double)dlugosc+1.0) + teraz +abs((double)Y + mmaxi * (double)cY -ys))) > 0.000001)
  130. mmaxi=((double)t-Y-teraz+ys)/(dlugosc+1ll+cY);
  131. mmaxi=floor(mmaxi);
  132. mmax=mmaxi;
  133. long long pom;
  134. if(floor(((double)ys-(double)Y)/(double)cY) == ((double)ys-(double)Y)/(double)cY)
  135. pom=(((double)ys-(double)Y)/(double)cY)-1;
  136. else pom=floor(((double)ys-(double)Y)/(double)cY);
  137. // cout<<" maksy "<<mmax<<" "<<pom<<"\n";
  138. mmax=min(mmax,pom);
  139. if(mmax>=mmin) wynik+=(mmax-mmin+1);
  140. }
  141. }
  142.  
  143. else if(rodz==2 && xs == X){
  144. double mmin=ceil(((double)ys-(double)Y)/(double)cY);
  145. if(mmin == ((double)ys-(double)Y)/(double)cY ) mmin++;
  146. //cout<<"mmin "<<mmin<<endl;
  147. if(mmin<0) mmin=0;
  148. if(t>=abs(Y-ys)+teraz){
  149. long long mmax;
  150. double mmaxi=((double)t+Y-teraz-ys)/(dlugosc+1ll-cY);
  151. if(abs((double)t - (mmaxi * ((double)dlugosc+1.0) + teraz +abs((double)Y + mmaxi * (double)cY -ys))) > 0.000001)
  152. mmaxi=((double)t-Y-teraz+ys)/(dlugosc+1ll+cY);
  153. mmaxi=floor(mmaxi);
  154. mmax=mmaxi;
  155. long long pom=floor(((double)ys-(double)nY)/(double)cY);
  156. //cout<<" maksy "<<mmax<<" "<<pom<<"\n";
  157. mmax=min(mmax,pom);
  158. if(mmax>=mmin) wynik+=(mmax-mmin+1);
  159. }
  160. }
  161.  
  162. else if(rodz == 1 && xs > X && xs <= nX ){
  163. double m=(((double)ys-(double)Y)/(double)cY);
  164. if(m==(long long)m && m >= 0){
  165. //cout<<"pokazuje "<<teraz<<" "<<abs(X-xs)<<" "<<m*(dlugosc+1ll)<<"\n";
  166. long long czas=teraz+abs(X+m*cX-xs)+m*(dlugosc+1ll);
  167. if(t>=czas) wynik++;
  168. }
  169.  
  170. }
  171. else if(rodz == 3 && xs < X && xs >= nX ){
  172. // cout<<"bada bing\n";
  173. double m=(((double)ys-(double)Y)/(double)cY);
  174. // cout<<m<<endl;
  175. if(m==(long long)m && m >= 0){
  176. // cout<<"twoja stara\n";
  177. // cout<<abs(X+m*cX-xs)<<endl;
  178. long long czas=teraz+abs(X+m*cX-xs)+m*(dlugosc+1ll);
  179. // cout<<"czas "<<czas<<endl;
  180. if(t>=czas) wynik++;
  181. }
  182. }
  183. rodz=starrodz;
  184. // cout<<wynik<<endl;
  185.  
  186. }
  187. void sprawdzdla43(int rodz,int i){
  188. int starrodz=rodz;
  189. if(ujem==false){
  190. if(rodz==1) {
  191. starrodz=rodz;
  192. rodz=3;
  193. }
  194. else if(rodz==3){
  195. starrodz=rodz;
  196. rodz=1;
  197. }
  198. }
  199. nY=Y+y[rodz]*ruchy[i];
  200. nX=X+x[rodz]*ruchy[i];
  201. if(rodz==1 && ys == Y){
  202. double mmin=ceil(((double)xs-(double)nX)/(double)cX);
  203. if(mmin<0) mmin=0;
  204. if(t>=abs(X-xs)+teraz){
  205. long long mmax;
  206. double mmaxi=((double)t+X-teraz-xs)/(dlugosc+1ll-cX);
  207. // cout<<t<<" "<<" "<<X<<" "<<xs<<" "<<cX<<dlugosc+1ll<<"\n";
  208. // cout<<"PIERW MMAXI "<<mmaxi<<"\n";
  209. // cout<<mmaxi * (double)(dlugosc+1ll) + teraz +abs((double)X + mmaxi * (double)cX -xs)<<"\n";
  210. if(abs((double)t - (mmaxi * ((double)dlugosc+1.0) + teraz +abs((double)X + mmaxi * (double)cX -xs))) > 0.000001){
  211. // cout<<t - (mmaxi * ((double)dlugosc+1.0) + teraz +abs((double)X + mmaxi * (double)cX -xs))<<"\n";
  212. // cout<<t<<" "<<(mmaxi * ((double)dlugosc+1.0) + teraz +abs((double)X + mmaxi * (double)cX -xs))<<"\n";
  213.  
  214. mmaxi=((double)t-X-teraz+xs)/(dlugosc+1ll+cX);
  215. }
  216. // cout<<mmaxi<<"\n";
  217. mmaxi=floor(mmaxi);
  218. // cout<<mmaxi<<"\n";
  219. mmax=mmaxi;
  220. long long pom;
  221. if(floor(((double)xs-(double)X)/(double)cX) == ((double)xs-(double)X)/(double)cX)
  222. pom=(((double)xs-(double)X)/(double)cX)-1;
  223. else pom=floor(((double)xs-(double)X)/(double)cX);
  224. mmax=min(mmax,pom);
  225. // cout<<"mmax mmin "<<mmax<<" "<<mmin<<"\n";
  226. if(mmax>=mmin) wynik+=(mmax-mmin+1);
  227. }
  228. }
  229.  
  230. else if(rodz==3 && ys == Y){
  231. double mmin=ceil(((double)xs-(double)X)/(double)cX);
  232. if(mmin == ((double)xs-(double)X)/(double)cX ) mmin++;
  233. // cout<<"mmin "<<mmin<<endl;
  234. if(mmin<0) mmin=0;
  235. if(t>=abs(X-xs)+teraz){
  236. long long mmax;
  237. double mmaxi=((double)t+X-teraz-xs)/(dlugosc+1ll-cX);
  238. if(abs((double)t - (mmaxi * ((double)dlugosc+1.0) + teraz +abs((double)X + mmaxi * (double)cX -xs))) > 0.000001)
  239. mmaxi=((double)t-X-teraz+xs)/(dlugosc+1ll+cX);
  240. mmaxi=floor(mmaxi);
  241. mmax=mmaxi;
  242. // cout<<t<<" "<<abs(X-xs)<<" "<<teraz<<" "<<dlugosc+1-cX<<endl;
  243. long long pom=floor(((double)xs-(double)nX)/(double)cX);
  244.  
  245. mmax=min(mmax,pom);
  246. // cout<<"mmin mmax "<<mmin<<" "<<mmax<<"\n";
  247. if(mmax>=mmin) wynik+=(mmax-mmin+1);
  248. }
  249. }
  250.  
  251. else if(rodz == 0 && ys > Y && ys <= nY ){
  252. double m=(((double)xs-(double)X)/(double)cX);
  253. // cout<<xs<< " "<<X<< " "<<cX<<"\n";
  254. // cout<<"rodz 0 m "<<m<<"\n";
  255. if(m==(long long)m && m >= 0){
  256. long long czas=teraz+abs(Y+m*cY-ys)+m*(dlugosc+1ll);
  257. if(t>=czas) wynik++;
  258. }
  259.  
  260. }
  261. else if(rodz == 2 && ys < Y && ys >= nY ){
  262. double m=(((double)xs-(double)X)/(double)cX);
  263. if(m==(long long)m && m >= 0){
  264. long long czas=teraz+abs(Y+m*cY-ys)+m*(dlugosc+1ll);
  265. if(t>=czas) wynik++;
  266. }
  267. }
  268. rodz=starrodz;
  269. // cout<<wynik<<endl;
  270.  
  271. }
  272.  
  273.  
  274. void rozwiaz1(int Q){
  275. dlugosc=-1;
  276. while(Q--){
  277. //cout<<Q<<" ah \n";
  278. for(int i=0; i<ruchy.size(); i++){
  279. dlugosc++;
  280. rodz++;
  281. if(rodz==4) rodz=0;
  282. //cout<<"ruch "<<ruchy[i]<<"\n";
  283. nY=Y+y[rodz]*ruchy[i];
  284. nX=X+x[rodz]*ruchy[i];
  285. sprawdz(rodz);
  286. X=nX;
  287. Y=nY;
  288.  
  289. dlugosc+=ruchy[i];
  290. //cout<<"dl "<<dlugosc<<" \n";
  291. //cout<<X<<" "<<Y<<"\n";
  292. }
  293.  
  294. }
  295. // cout<<"pozyjcje\n";
  296. // for(auto it:pozycje) cout<<it<<" ";
  297. //cout<<dlugosc<<" "<<wyst<<"\n";
  298. pozycje.push_back(dlugosc+1);
  299. //cout<<"dlugosc "<<dlugosc<<"\n";
  300. if(wyst==0) cout<<0;
  301. else if(t<dlugosc) cout<<wynik+binsearch(t);
  302. else{
  303. t-=dlugosc;
  304. wynik+=wyst;
  305. wynik+=((t/(dlugosc+1ll))*wyst);
  306. t-=((t/(dlugosc+1ll))*(dlugosc+1ll));
  307. // cout<<wynik<<endl;
  308. // cout<<t<<endl;
  309. // for(auto it: pozycje){
  310. // cout<<it<<" ";
  311. // }
  312. // cout<<endl;
  313. // cout<<binsearch(t);
  314. cout<<wynik+binsearch(t-1);
  315. }
  316. }
  317. void czter(){
  318. for(int i=0; i<ruchy.size(); i++){
  319. dlugosc++;
  320. rodz++;
  321. if(rodz==4) rodz=0;
  322. nY=Y+y[rodz]*ruchy[i];
  323. nX=X+x[rodz]*ruchy[i];
  324. X=nX;
  325. Y=nY;
  326. dlugosc+=ruchy[i];
  327. }
  328. cX=X;
  329. cY=Y;
  330. if(X!=0 && Y!=0){
  331. X=0;
  332. Y=0;
  333. for(int i=0; i<ruchy.size(); i++){
  334. //cout<<"ruch "<<ruchy[i]<<"\n";
  335. teraz++;
  336. rodz++;
  337. if(rodz==4) rodz=0;
  338. //cout<<"nowe "<<nX<<" "<<nY<<"\n";
  339. sprawdzdla41(rodz,i);
  340. Y=nY;
  341. X=nX;
  342. // cout<<X<<" "<<Y<<endl;
  343. teraz+=ruchy[i];
  344. }
  345. cout<<wynik;
  346. }
  347. else if(Y!=0){
  348. Y=0;
  349. if(cY<0) {
  350. ujem=false;
  351. cY*=-1;
  352. ys*=-1;
  353. }
  354. for(int i=0; i<n; i++){
  355. teraz++;
  356. rodz++;
  357. if(rodz==4) rodz=0;
  358. nY=Y+y[rodz]*ruchy[i];
  359. nX=X+x[rodz]*ruchy[i];
  360. sprawdzdla42(rodz,i);
  361. X=nX;
  362. Y=nY;
  363. teraz+=ruchy[i];
  364. }
  365. cout<<wynik;
  366. }
  367. else if(X!=0){
  368. if(cX<0){
  369. ujem=false;
  370. cX*=-1;
  371. xs*=-1;
  372. }
  373. X=0;
  374. for(int i=0; i<n; i++){
  375. teraz++;
  376. rodz++;
  377. if(rodz==4) rodz=0;
  378. nY=Y+y[rodz]*ruchy[i];
  379. nX=X+x[rodz]*ruchy[i];
  380. sprawdzdla43(rodz,i);
  381. X=nX;
  382. Y=nY;
  383. teraz+=ruchy[i];
  384. }
  385. cout<<wynik;
  386. }
  387. else rozwiaz1(1);
  388.  
  389.  
  390.  
  391.  
  392. }
  393. int main(){
  394. ios_base::sync_with_stdio(0);
  395. cin.tie(0);
  396. cout.tie(0);
  397. cin>>n>>t;
  398. pozycje.push_back(0);
  399. for(int i=0; i<n; i++){
  400. int a;
  401. cin>>a;
  402. ruchy.push_back(a);
  403. }
  404. cin>>xs>>ys;
  405. if(xs==0 && ys==0) wynik++;
  406. if(n%4==0) czter();
  407. else if(n%2==0) rozwiaz1(2);
  408. else rozwiaz1(4);
  409. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!