Common Boarda=[] for i in range(int(input())): c=str(input()) if len(a)==0 : a.append(c) continue d=(a[0].split())[1] d=int(d) k=int((c.split())[1]) if k>=d : a.reverse() a.append(c) a.reverse() else: for j in range (len(a)): h=int((a[j].split())[1]) if k >= h: p = a[:j] o = a[j:] p.append(c) p.extend(o) for i in range(len(a)): print(a[i]) Edited by author 26.09.2018 20:38 the number of integer point inside circle is sigma(r*r/(4*i+1)-r*r/(4*i+3)) use stern borcot to cut hyperbola curve it can be done O(r^(2/3)) what do you mean by cut huperbola curve? maybe we can directly use stern borcot tree to cut circle I think it is faster... basic idea is use line segment (x1,y1) --->(x2,y2) with slope -a/b(a>0,b>0) to cut quadric curve so that all of integer point strictly under this line segment is inside the quadric curve (x1,y1) and (x2,y2) is strictly outside the curve if we know (x1,y1),(x2,y2) and -a/b we can find next -(a1/b1) a/b and a1/b1 is neibour in stern borcot tree .it can be proved there are O(n^1/3) state if the quadric curve is huperbola curve x*y==n My solution convert this problem to compute simga(r*r/(4*i+1)-r*r/(4*i+3)) so it is huperbola curve (4*x+1)*y==r*r and (4*x+3)*y==r*r I have done twice ,so it is slow, dirctly cut circle only do once... Edited by author 25.09.2018 21:34 Edited by author 25.09.2018 21:37 will try that for sure, I don't see any way I can speed up my current solutoin, I only need to calculate squares n-(n/sqrt(2)) times, and I do only +/- operations per iteration(no sqrt and multiplication/divisions). and for any n, it runs 0.75-0.8 sec on my pc, but I still get TLE18 here. your computer is too strong, ural oj O(1e9) can't fit into 2 sec Edited by author 26.09.2018 20:03 int main() { optimize(); int n,k; cin>>n>>k; k--; int z=k; bool b=0; int a[n+10]; for(int i=0;i<n;i++) { if(k!=0) { if(b==0) { a[i]=k; b=1; z--; } else { if(z==0) { a[i]=0; k=0; b=1; continue; } a[i]=-k; k--; b=0; z--; if(z==0) k=0; } } else a[i]=0; //dbg(z); } for(int i=n-1;i>=0;i--) cout<<a[i]<<" "; //return main(); } when going to print 0 0 -3 3 or -3 3 0 0 I am getting WA..But When I print 0 0 -1 1 I get AC..Why?what is the difference between 1st two case and last one??Can anyone explain me?? Thanks to Oleksandr Kulkov for preparing! Thanks I almost have no problem to do on ural why is k =10 and n =2 output =90 #include <stdio.h> #include <stdlib.h> #include <math.h> int main() { unsigned long long k[4]; for(int i=0;i<4;i++){ scanf("%llu",&k[i]); } printf("\n"); printf("%.4f\n",sqrt(k[3])); printf("%.4f\n",sqrt(k[2])); printf("%.4f\n",sqrt(k[1])); printf("%.4f\n",sqrt(k[0])); return 0; } Ошибка на тесте 2 /Error in test 2 Edited by author 09.09.2018 15:45 Во входном потоке может быть любое количество чисел, а не только четыре. Почините алгоритм проверки! Не контачит на сях. Вот код: #include <stdio.h> int main(int argc, char const *argv[]) { int a, b; a=1, b=5; printf("%i\n", a+b); return 0; } а с чего ты взял что вводимые данные будут целочисленные? В этом коде не считываются a и b из входного потока. Edited by author 23.09.2018 18:34 Hello, everyone. Just wanted to summarize some info about this problem. Ok, my code got AC with following things in it: 1. My pi was 3.1415926535897932384626433 (perhaps it is enough) 2. I used this formula from wikipedia deltaArc=acos(sin(phiA)*sin(phiB)+cos(phiA)*cos(phiB)*cos(deltaL)); distance = deltaArc*3437.5; (see the first formula from wikipedia http://en.wikipedia.org/wiki/Great-circle_distance)3. I used the following condition: if(100.00-distance>0.005) printf("DANGER!\n"); Hope it will help somebody. thanks a lot ...your formula is really useful.^_^ Used everynth what is written here. However still WA8. Any new ideas?... Do u know that pi can be calculated by this formula: atan(1) * 4? 1)Solution always exists and his complexity <= O(n^2) 2)Try to solve the problem when the permutation is n (n-1) ... (n-left+1) 1 2 3 ... right where left+right=n. After O(n^2) steps you can get n 1 2 3 ... (n-1). Then after O(n^2) steps you can get 1 2 3 ... n. 3)Try to reduce the problem to this permutation by O(n^2) steps. 4)Good to know: 1 2 3 ... t x-> 2 1 3 ... t x -> 3 1 2 4 ... t x -> 4 1 2 3 5 ... t x ->... -> t 1 2 3 ... (t-1) x -> x 1 2 3 ... t by t steps. I call this operation "Shift(t)". Edited by author 26.07.2018 20:20 simplest solution: i=0..n-1 : while p[i] <> n do change(p[i]); Edited by author 22.09.2018 14:02 I can't think of a way to store goto and fail transitions of so many vertices and avoid MLE. please help. here's code: #include <stdio.h> #include <queue> using namespace std; short g[110000][256]; short f[110000]; short o[110000]; short n,m,newstate=0; queue<short>Q; int main(void){ short i,pos=0,q,r,u,v,ch,state; scanf("%hd",&n);getchar(); for(i=1;i<=n;++i){ r=0; ch=getchar(); state=0; ++r; ch+=128; while(g[state][ch]){ state=g[state][ch]; ch=getchar(); ++r; ch+=128; } while(ch!='\n'+128){ newstate=newstate+1; g[state][ch]=newstate; state=newstate; ch=getchar(); ++r; ch+=128; } o[state]=r-1; } for(i=0;i<256;++i){ if(q=g[0][i]){ f[q]=0; Q.push(q); } } while(!Q.empty()){ r=Q.front(); Q.pop(); for(i=0;i<256;++i){ u=g[r][i]; if(!(u==0&&r>0)){ Q.push(u); v=f[r]; while(g[v][i]==0&&v>0) v=f[v]; f[u]=g[v][i]; if(o[u]==0) o[u]=o[f[u]]; } } } scanf("%hd",&m);getchar(); for(i=1;i<=m;++i){ q=0;r=0; while((ch=getchar())!='\n'){ ch+=128; ++r; while(g[q][ch]==0&&q>0) q=f[q]; q=g[q][ch]; if(o[q]){ printf("%hd %hd",i,r-o[q]+1); return 0; } } } printf("Passed\n"); return 0; } you got pretty close, modified your solution to get AC. let me know if you need hints :) ikhomeriki@gmail.com Edited by author 21.09.2018 23:04 For TC: abracadabra abrabracada why don't the prefixes are: abra abracada a? and also why for TC: abracadabra arbadacarba the prefix is not: a? why don't the prefixes are: abra abracada a? You can write this prefixes, this is the correct answer. why for TC: abracadabra arbadacarba the prefix is not: a? Because the word must consist entirely of prefixes. #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n,count = 1; long long m, sum = 0; vector<long long> coll; vector<pair<long long, int>> coll1; cin >> n; while(n--) { cin >> m; coll.push_back(m); } m = coll[0]; int i = 1; if(coll.size() > 3){ for( ; i < coll.size(); ++i) { if(m <= coll[i] && count < 3) { count++; } else if( i>=3) { sum += coll[i-1]; sum += coll[i-2]; sum += coll[i-3]; coll1.push_back({sum, i-1}); sum = 0; count = 1; } m = coll[i]; } sort(coll1.begin(), coll1.end()); cout << coll1[coll1.size()-1].first << ' ' << coll1[coll1.size()-1].second << endl; } else cout << accumulate(coll.begin(), coll.end(), 0) << ' '<<'2' << endl; coll.clear(); coll1.clear(); return 0; } Irakli Khomeriki Stats 21 Sep 2018 01:24 It would be awesome to have stats for each task, like best/average time/memory of AC-ed solutions for each language. 4 0 0 0 0 0 Edited by author 23.05.2007 21:03 thanks, buddy it helped me use ios_base::sync_with_stdio(false); cin.tie(0); with cin/cout. Don't forget to add last two digit's sum carry if it has. 5M is too much. It isn't necessary to get whole numbers in memory. if you read data as: double x; cin>>x; a[i]=x*100; it doesn't work! |
|