|
|
back to boardWhy TL 11? Posted by yutr777 26 Oct 2013 14:26 #include <stdio.h> #include <vector> #define pb push_back #define For(i,n) for(int i=0;i<n;i++) using namespace std; int main() { int n,m,k; vector < int > w; vector < int > v; scanf("%d%d%d",&n, &m, &k); For(i,n) { int x; scanf("%d", &x); w.pb(x); } For(i,m) { int x; scanf("%d", &x); x--; v.pb(x); } int ind=0; int tek=0; int ans=0; long long i=0; vector < int > solve; while (true) { if (ind<v.size() && i==v[ind]) { int kol=0; while (kol<=k && solve.size()>0) { w.pb(solve[solve.size()-1]); solve.pop_back(); kol+=w[w.size()-1]; } ind++; i++; continue; } solve.pb(w[0]); w.erase(w.begin()); i++; if (w.size()==0 || solve.size()==n)break; } printf("%d", i); } Re: Why TL 11? Posted by kot 26 Oct 2013 15:23 I have WA 11. My solution very similar to yours. I don't have any idea what is wrong. BTW. If you use long long, you must use %lld in printf instead %d. #include <stdio.h> int n,m,k; int w[10000]; int t[10000]; long long d; void swap(int i, int j) { int t; t = w[i]; w[i] = w[j]; w[j] = t; } int caving(int i) { int s = 0; int c = 0; int j; while ((s <= k) && (i > 0)) { i--; s += w[i]; c++; } /*for (j = 0; j < c/2; j++) { swap(i+j,i+c-j-1); }*/ return c; } int main() { int i,j; int cw, ct; #ifndef ONLINE_JUDGE freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); #endif scanf("%d %d %d\n", &n, &m, &k); for (i = 0; i < n; i++) scanf("%d", &w[i]); for (i = 0; i < m; i++) scanf("%d", &t[i]); cw = 0; ct = 0; d = 0; do { d++; if ((ct < m) && (t[ct] == d)) { ct++; cw -= caving(cw); } else cw++; } while (cw < n); printf("%lld\n", d); return 0; } Re: Why TL 11? Hello, Kot! > int w[10000]; > int t[10000]; >> 1 ≤ n, m ≤ 10^5 I think yon need [100000] arrays. I had a step-by-step solution which caused TL 11. I've improved it to event-by-event solution but nothing changed. I translated it from Java to Visual C 2010 using your data loader and got WA11. Replaced w[10^4] by w[10^5] - and finally I've got TL11. I don't have any good idea and wonder about better algorithm or a bug which causes an endless loop... Could you try to fix it and write your solution result? Re: Why TL 11? Posted by Leonid 27 Oct 2013 22:02 Brute force solution works fine after some optimizations. Look at n and m limits - it is possible that Luke will drop same stones more than once. Re: Why TL 11? Finally my solution has been accepted. It's definitely a brute force one, but using optimization for all loops, which can be run undefined number of times. Re: Why TL 11? did you use binary search in your solution? |
|
|