Common BoardWhat's wrong? #include<cstdio> using namespace std; const int N=201; struct Node{int x,y;}a[N]; struct Line{int s,t;}b[N]; int fa[N],n,m,root; inline int direct(Node x,Node y,Node z){ return (y.x-x.x)*(z.y-x.y)-(y.y-x.y)*(z.x-x.x); } bool online(Node x,Line y){//right Node be=a[y.s],en=a[y.t]; if (x.x<be.x||x.x>en.x) return 0; if (direct(be,x,en)==0) return 1; return 0; } bool cross(Line x,Line y){ Node p1=a[x.s],p2=a[x.t],p3=a[y.s],p4=a[y.t]; if (online(p1,y)||online(p2,y)||online(p3,x)||online(p4,x)) return 1; int d1=direct(p1,p2,p3),d2=direct(p1,p2,p4),d3=direct(p3,p4,p1),d4=direct(p3,p4,p2); if ((d1^d2)<0&&(d3^d4)<0) return 1; return 0; } int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);} void unite(int x,int y){ x=find(x); y=find(y); if (x<y) fa[y]=x; else if (x>y) fa[x]=y; } int main(){ scanf("%d%d",&n,&m); for (int i=1; i<=n; i++) fa[i]=i; for (int i=1; i<=n; i++) scanf("%d%d",&a[i].x,&a[i].y); for (int i=1; i<=m; i++){ scanf("%d%d",&b[i].s,&b[i].t); unite(b[i].s,b[i].t); for (int j=1; j<=n; j++)if (online(a[j],b[i])) unite(j,b[i].s); for (int j=1; j<i; j++) if (cross(b[i],b[j])) unite(b[i].s,b[j].s); } root=find(1); for (int i=2; i<=n; i++) if (find(i)!=root) {printf("NO"); return 0;} printf("YES"); return 0; } My algo is O(p*n*logn). Algo: 1)sort pairs <d,s> by d. We get d1<=d2<=d3<=...<=dn. s1 s2 s3 sn 2)For each p we choose a minimal k (if exist pairs <ki,p> and <kj,p> where ki<kj then we delete <kj,p> 3)ans=s[1]+...+s[n]-(x1+x2+...+xn)/100 where xi=s[i]*di or xi=s[i]*p if we choose p (if we choose p => the minimum of the k elements of x are equal to s*p), i=1..n => we must max_sum=(x1+x2+...+xn)->max =>ans=s[1]+...+s[n]-max_sum/100 4)max_sum=s1*d1+...+sn*dn For each p=1..100 find 1<=j<=n | p<dj, j->min (if there is no such j => max_sum=max(max_sum, (s[1]+...+s[n])*p) ) then we take (s[1]+...+s[j-1])*p (s[0]=0); if we took <k elements then we must take lost=k-(j-1) elements from sj,...,sn. We must choose such index i1<i2<...<ilost from j..n | s[i1]*(d[i1]-p)=min(s[i]*(d[i]-p), j<=i<=n, s[i2]*(d[i2]-p)=min(s[i]*(d[i]-p), j<=i<=n,i!=i1, ... . then max_sum=max(max_sum, (s[1]+...+s[j-1])*p + (s[i1]+...+s[ilost])*p+Sum(si*di, j<=i<=n and i<>ik,k=1..lost)). Edited by author 28.06.2017 15:34 My solution passes first 4 test cases and shows memory limit exceeded error at 5th test case. I have made a global 4D array 100*100*100*100 which keeps the result of the sum of a rectangle whose top left corner is x1,y1 and bottom right corner is x2,y2, 4d array mat[x1][y1][x2][y2] stores the sum of the numbers corresponding to that rectangle. Now if this big array were a reason behind memory limit exceeded error than it shouldn't have passed even the first test cases because i made global 4d array of maximum size by default. So what can be the reason? #include <iostream> using namespace std; const int M = 107; int mat[M][M][M][M]; int main() { int n; cin >> n; int arr[n][n]; int ans = -1e9; for (int i=0; i<n; i++) for (int j=0; j<n; j++) { cin >> arr[i][j]; mat[i][j][i][j] = arr[i][j]; if (arr[i][j] > ans) ans = arr[i][j]; } for (int size = 2; size<=n*n; size++) { for (int p=1; p<=size and p<=n; p++) { int q = size/p; if (p*q != size) continue; for (int i=0; i<n-p+1; i++) { for (int j=0; j<n-q+1; j++) { int x1 = i, y1 = j; int x2 = i+p-1, y2 = j+q-1; if (x2-x1 > y2-y1) { mat[x1][y1][x2][y2] = mat[x1][y1][x2-1][y2] + mat[x2][y1][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } else { mat[x1][y1][x2][y2] = mat[x1][y1][x2][y2-1] + mat[x1][y2][x2][y2]; if (mat[x1][y1][x2][y2] > ans) ans = mat[x1][y1][x2][y2]; } } } } } cout << ans << endl; } Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:06 Edited by author 26.06.2017 17:07 Actually, if you don't access your global allocated memory, that memory don't counts. I have noticed that when watching how my solutions are testing. When there is a global array of big size first few cases are low memory. And last test cases are high memory usage. You can find any simple task were you are to output some string. Allocate a HUGE buffer for that string. Then submit your solution. Then allocate a buffer just enough to hold your string and submit again. And you will see that memory usage is the SAME. Why if I am trying to precalculate factorials using unsigned long long int there is WA#5? There are 64 last binary digits digits and in this task we are to output at most 32 binary digits. There are no tests where N=0 xD) #include<cstdio> #include<cstring> #include<iostream> #define pii pair<int,int> #define pdd pair<double,double> #define mp make_pair #define F first #define S second #define N 210 using namespace std; int n,m; int fat[N]; pii e[N]; pdd p[N]; int father(int x) {if(fat[x]!=x) fat[x]=father(fat[x]); return fat[x];} double calc(pii a,pii b,pii c) {return (a.F-c.F)*(b.S-c.S)-(b.F-c.F)*(a.S-c.S);} bool judge(pii a, pii b, pii c, pii d) { if (max(a.F,b.F)<min(c.F,d.F)||max(a.S,b.S)<min(c.S,d.S)||max(c.F,d.F)<min(a.F,b.F)||max(c.S,d.S)<min(a.S,b.S)) return false; if (calc(c,b,a)*calc(b,d,a)<0||calc(a,d,c)*calc(d,b,c)<0) return false; return true; } int main() { int i,j,x,y; scanf("%d %d",&n,&m); for(i=1;i<=n;i++) fat[i]=i; for(i=1;i<=n;i++) {scanf("%lf %lf",&x,&y); p[i]=mp(x,y);} for(i=1;i<=m;i++) {scanf("%d %d",&x,&y); e[i]=mp(x,y); fat[father(x)]=father(y);} for(i=m+1;i<=m+n;i++) e[i]=mp(i-m,i-m); m+=n; for(i=1;i<=m;i++) for(j=i+1;j<=m;j++) if(judge(p[e[i].F],p[e[i].S],p[e[j].F],p[e[j].S])) fat[father(e[i].F)]=father(e[j].F); int stan=father(1); for(i=1;i<=n;i++) if(father(i)!=stan) puts("YES"); return 0; } Just output n random numbers. After that, output m random numbers. All random numbers are in range [1;1e9]. AC first attempt. At first I wrote a tricky solution using trigonometry and binary search. And I was unable to pass through test case No. 12. Then I wrote simple two-step solution and got AC. Can somebody write input? I can't write input. I might suggest you are printing numbers X wrong. Or you are allocating not enough space. Or you are using too deep recursion. I wrote program on C++ and got WA1. I rewrote program on Pascal and got AC. I think my error in input string. How do i read lines? My attempts: 1) int c; n=0; while ((c = getchar()) != EOF) { if(c=='\n') break; s[++n]=c; } m=0; while ((c = getchar()) != EOF) t[++m]=(char)c; 2) void Input() { int c; scanf("%c",&c); n=0; while (c!='\n') { s[++n]=c; scanf("%c",&c); } m=0; while ((c = getchar()) != EOF) t[++m]=(char)c; } Probably <string> will help, but i prefer work with index>=1. Edited by author 22.06.2017 23:44 Edited by author 22.06.2017 23:44 Used DP + BIT, AC in 0.078 O(n*k*logn) solution. Don't forget, % 10^9 every step. My approach wrong approach is such. Read cur number X. Find CNT count of numbers Y (Y>X) already read. Find number of ways to pick K-1 items from set of CNT distinctive items. Add that number to ANSWER. Find modulo. Edited by author 11.05.2017 13:28 Your solution is wrong. See for example 6 3 3 4 5 6 2 1 when you read 2, all the numbers before it are > 2 and hence you'll add to your sum, all the possible pairs in previous 4 numbers. But 3 4 5 6 can't make any pair such that a_i > a_{i+1}. Hence your solution doesn't work. Edited by author 22.06.2017 13:55 After we add new pile Z of stones if there is new pair of piles X and Y such that |X-Y| is minimal that either X=Z or Y=Z. So, just add nee pile and recalculate new pair of piles such that the difference between stones count is minimal in O(n) where n is tje number of piles present now. import java.util.Scanner; /** * Created by macbookpro on 2/19/15. */ public class JavaThieves877 { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int c1 = Integer.parseInt(scanner.nextLine()); int c2 = Integer.parseInt(scanner.nextLine()); if(c1 % 2==0 || c2 % 2!=0 ) { System.out.print("Yes"); } else if(c1 % 2 != 0 || c2% 2== 0) { System.out.print("No"); } } } Nevermind I didn't read that this is running well:) Edited by author 21.06.2017 04:49 Some tests? You can try use these tests: 4999 12832 ->2455.1680336 5000 12345 ->2490.9210000 4987 9999 ->50.7443353 1234 3456 ->394.1183144 2976 6547 ->952.8800403 3487 8000 ->1448.9340407 4955 11111 ->1820.5574168 456 968 ->99.1228070 43 123 ->10.4651163 1 2 ->1 4 9 ->2.2500000 3 9 ->0 2 5 ->1.5 2 4 ->1 4399 13013 ->352.6492385 4321 9923 ->1803.1751909 4001 10500 ->1877.1534616 4000 10001 ->2000.4992500 4000 10000 ->2000.5000000 4123 9999 ->2015.9083192 At first I thought I was getting WA's because of the wrong minus sign. Actual reason was printing integers. I was trying to print integers using just PUTCHAR. Of course it worked fine for 0-9. And was failing for other numbers. I tried to solve it with C++. It was long. It was PAINFUL! Finally, I didn't managed to solve it in C++. And then I just opened my Python IDE and solves it within 10 minutes. Just AC first attempt. The task is evil. The product of natural numbers with a given condition in this problem will be maximal if and only if the middle arithmetic of these numbers is the most closely to the number e=2.71828... It's a mathematical sentence which are proved! P.S. Sorry for my bad English Why is that true? You can get AC without math :P Well, you only need to understand that optimal partition can't contain any x >= 4(as 2*(x-2) >= x in this case), it obviously can't contain ones, and it can't contain more than 2 copies of 2, as 2*2*2<3*3. Surpisingly, there is only one way to express any x >= 2 as sum of 3's and not more than two 2's. That's a very nice idea. Let me clarify it for those who had problems understanding bsu.mmf.team's English. First of all, 'middle arithmetic' is an arithmetic mean. The thing is, the product will be maximal if (a_1 + a_2 + ... + a_n) / n ≈ e. Well, it's not hard to figure out that the output of the program should be something like that: 3 * 3 * 3 * ... * ? used RMQ using segment tree to find lca in log(n) total time complexity O(n+q*(lgn)) = O(q*lgn) Almost the same numbers (0.268, 11500) for table for 2^i -th ancestor. |
|