Some AC to try this test BID 0.01 BID 10000 BID 5000 BID 5000 SALE 5000 3 DEL 5000 SALE 3000 3 SALE 0.01 3 QUIT For God's sake, use ans/100 instead of ans*0.01f But i don't know why journ = [] x = 0 k = 0 sold = 0 cmd = ',,' while cmd[0] != 'QUIT': cmd = input().split() oper_name = cmd[0] if cmd[0] == 'BID': x = cmd[1] journ.append(x) elif cmd[0] == 'DEL': x = cmd[1] journ.remove(x) elif cmd[0] == 'SALE': x = cmd[1] k = int(cmd[2]) for i in journ: if float(i) >= float(x): k -= 1 sold += 1 else: continue print(sold * 0.01) What is wrong ? I got time limit in test#5 and I can't find out why if you are using G++ 7.1 try using visual studios 2017 compiler. Apparently one works faster than the other if you write on C++ may be such change help: scanf("%Lf", &a); x = a * 100.0 //- WA test 6 x = floorl(a * 100.0 + 0.5) //- AC Edited by author 10.09.2004 18:33 Edited by author 10.09.2004 18:33 i have WA6 for correct input of price use procedure like this int read_price(void) { double f; fscanf(inf,"%lf",&f); return (int)((f+1e-9)*100.0); } and you got AC Thank you very much!I got AC Can you explain me please when expressions (int) (f * 100) and (int)((f+1e-9)*100.0)can differ. (I got AC after using this method, but still can't figure out what the problem is). Thanks in advance :) Edited by author 07.10.2013 03:17 I don't understand ! Why when I read data like integer before and after point : int price = before * 100 + after -> is wa6 and when I read data like double: double d; scanf("%lf, &d); int price = (int)(d * 100.0 + 0.1) -> is ok My program uses only 850K of memory!!! Two days of troubles and the best solution was written! If you are intrested in it leave your mail here. I've solved this problem via interval tree, but it uses 4 Mbytes. I don't need your code, but could you explain your algorithm? My e-mail is dimanyes@yahoo.com I think, that he have used Fenwick tree No :) This solution uses Cartesian tree. My best solution which uses Fenwick's tree uses about 1400K of memory PS: Good luck on the ROI, Ilya :) Can you say book's names where these tree are described? I've modified this solution... Now it uses only 630K of memory!!! (Random Trees are very useful :) can i do it without trees ? like this #include<iostream> #include<string> using namespace std; void limit_to_two_num(float &price) { price=price*100; price=static_cast<int>(price); price=(price)/100; } void main() { int check=0,quantity,length=0; string str="\0"; float price; float profit=0; float arr[100000]; while(str!="QUIT" && check!=100000) { cin>>str; if(str=="BID") { cin>>price; limit_to_two_num(price); arr[length++]=price; check++; } else if(str=="DEL") { cin>>price; limit_to_two_num(price); for(int i=0;i<length;i++) { if(arr[i]==price) { for(int j=i;j<length-1;j++) { arr[j]=arr[j+1]; } length--; break; } } check++; } else if(str=="SALE") { cin>>price; limit_to_two_num(price); cin>>quantity; for(int i=0;i<length;i++) { if(arr[i]>=price) { profit=profit+0.01; } } } } cout<<"Total profit: "<<profit<<endl; } i can't solve this problem.Please help... yu1178209138@hotmail.com i have wa on 2 test.can someone help me.i'm trying to solve it with fenwick. I got problem in test#1. please help Edited by author 15.11.2015 23:24 Problem was solved. Edited by author 04.06.2015 18:02 Could someone tell me how to input double fast in C++ ? scanf is not fast enough Edited by author 25.11.2014 08:55 I have solved this problem by Fenvic tree, at first I got WA on 5 test, then I changed int-s into long long-s and now I have WA on 6 test. If you had this kind of experience please tell me what types should I use to get AC? Thanks. The test 6 aint about data types' ranges. იდეაში, ეგ ხო ფენვიკის ხით უნდა გავიდეს, მე ვთვლი რაოდენობას, რამდენი გაყიდვა შესრულდება და შემდეგ ვამრავლებ 0.01–ზე და ვაბეჭდინებ. და ეგრე უნდა მუშაობდეს წესით ხო? Try this test BID 0.01 SALE 0.02 10 Answer:0.00 #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<stdlib.h> #include<cmath> using namespace std; #define N 1000000 #define LL long long #define lowbit(x) x&(-x) LL re[N+10]; void add(int x,int d) { while(x) { re[x]+=d; x-=lowbit(x); } } LL getsum(int x) { LL s = 0; while(x<=N) { s+=re[x]; x+=lowbit(x); } return s; } int main() { int num; LL sum=0; double k; char s[20]; while(scanf("%s",s)!=EOF) { if(s[0]=='Q') break; else if(s[0]=='B') { scanf("%lf",&k); int kk = floorl(k*100.0+0.5); add(kk,1); } else if(s[0]=='D') { scanf("%lf",&k); int kk = floorl(k*100.0+0.5); add(kk,-1); } else { scanf("%lf %d",&k,&num); int kk = floorl(k*100.0+0.5); LL ss = getsum(kk); if(ss>=num) sum+=num; else sum+=ss; } } printf("%.2lf\n",(double)sum/100.0); return 0; } help!! My solution, which didn't pass stress-test, get AC! WA7, and I want to know is it round problem or fault in my data structure. Tests like test7 will be very helpful for me Edited by author 06.08.2011 14:27 With recent changes to statement sample became wrong; I think sample input should now look like: BID 0.01 BID 10000.00 BID 5000.00 BID 5000.00 SALE 7000.00 3 DEL 5000.00 SALE 3000.00 3 SALE 0.01 3 QUIT , am I right? We have replaced "exactly 2 digits" by "at most 2 digits" in the problem statement. Thank you. Rus: Покупатели заявляют цену, по которой они готовы купить (от 0.01 до 10000.00 бибриков). Eng: Customers make their bids: announce a price at which they are ready to buy a pig (the price is between 0.01 and 10000.00 bibriks and always has exactly 2 digits after the decimal point). There is no analog of "and always has exactly 2 digits after the decimal point" in Russian statement which significantly complicate solution. what's wrong on earth? thanks all First I got WA ON 5. I changed longint into int64 then WA ON 6 :( Then changed trunc into round,got AC. Round what ? Can you explain ? I use Int64, too . I write result : Writeln(Profit/100:0:2) ; Why it's wrong ? Please help me ! I use long long int type and rigth read-write operations. But also have WA#6. Who can help me? #include <cstdio> #include <algorithm> #include <cmath> using namespace std; #define left(x) ((x) << 1) #define right(x) ((x) << 1 | 1) #define parent(x) ((x) >> 1) enum CmdType {BID,DEL,SALE}; struct { int price,c; enum CmdType cmd; } data[100000]; struct { int l,r,v; } tree[265000]; int n,size,sz,bnd[100100],bnds[100100],bndc,bndsc; char buf[20]; int query(int price) { int ans = 0; int v = 1; while (v < sz && tree[v].v > 0) if (price <= tree[left(v)].r) v = left(v); else { ans += tree[left(v)].v; v = right(v); } return ans+tree[v].v; } void add(int price, int delta) { int v = 1; while (v < sz) { tree[v].v += delta; if (price <= tree[left(v)].r) v = left(v); else v = right(v); } tree[v].v += delta; } void main() { #ifndef ONLINE_JUDGE freopen("data.txt","r",stdin); #endif n = bndsc = 0; bnds[bndsc++] = 0; bnds[bndsc++] = 1000000; while (true) { gets(buf); if (buf[0] == 'Q') break; double t; if (buf[0] == 'S') { sscanf(buf+4,"%lf%d",&t,&data[n].c); data[n].cmd = SALE; } else { sscanf(buf+4,"%lf",&t); if (buf[0] == 'B') data[n].cmd = BID; else data[n].cmd = DEL; } data[n].price = 1000000-floorl(t*100.0+0.3); if (data[n].cmd == SALE) bnds[bndsc++] = data[n].price; n++; } sort(bnds,bnds+bndsc); bnd[0] = bnds[0]; bndc = 1; for (int i = 1; i < bndsc; i++) if (bnds[i] != bnds[i-1]) bnd[bndc++] = bnds[i]; bndc--; for (sz = 1; sz < bndc; sz*=2); for (int i = 0; i < bndc; i++) { tree[sz+i].l = bnd[i]+1; tree[sz+i].r = bnd[i+1]; tree[sz+i].v = 0; } for (int i = sz-1; i >= 1; i--) { tree[i].l = tree[left(i)].l; tree[i].r = tree[right(i)].r; tree[i].v = 0; } long long ans = 0; for (int i = 0; i < n; i++) if (data[i].cmd == SALE) { int v = query(data[i].price); if (v > data[i].c) v = data[i].c; ans += v; } else if (data[i].cmd == BID) add(data[i].price,+1); else add(data[i].price,-1); printf("%.2lf",(ans*0.01)+1.e-5); } That's true! I also had WA#6 and then changed trunc into round and got AC! Why I always get WA on #4? Did anybody try to solve this problem via "splay trees" (self-organizing trees by Sleator)? Randomized trees and treaps easily accepted, but now I'am interested in splay trees and always TL :( |
|