Общий форумПоказать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | That testing supercomputer though | Chitanda Eru | 1972. Тестирование игры | 19 мар 2017 00:15 | 1 | So, i accidentally wrote a suboptimal solution for this problem (stored entire sequences of settings instead of just singular changes from the previous ones), saw it taking 15s (about 8 without the output) to complete max test on my laptop but submitted for fun anyway. Got AC in 0.4s. Go figure. | a stronger version | Shen Yang | 1797. Summit Online Judge. Версия 2 | 18 мар 2017 10:48 | 1 | | Please HELP ME WA 14 | Shohruh_1999 | 1607. Такси | 18 мар 2017 09:29 | 1 | #include<iostream> #include<math.h> #include<algorithm> #include<string.h> using namespace std; int a,b,c,d; int main() { cin >> a >> b >> c >> d; int h = c; if(a >= c) { cout << a; return 0; } while(1) { if(a == c) { cout << a; return 0; } a+=b; if(c-d >= a) c-=d; else { if(a > h) cout << h; else cout << a; return 0; } } return 0; } | How to pass it below 0.015s? | LittlePig | 1584. Тайны фараонов | 17 мар 2017 19:37 | 5 | This is one time matching? I used my solution for 1076. | Max tests | Chitanda Eru | 1159. Fence | 17 мар 2017 15:37 | 1 | For the max test (a hundred 100's) the answer is 7955128.99. For ninety nine 1m sides and one 98m side it's 397.86. Use this to check your precision. | Funny. | Mukhametianov Den [USU] | 1159. Fence | 17 мар 2017 15:32 | 3 | Funny. Mukhametianov Den [USU] 28 авг 2010 19:10 infin = 100000000 - wa14. infin = 1000000 - ac. Re: Funny. Sergey Lazarev (MSU Tashkent) 4 янв 2011 23:45 Thank you! But it's very strange. I found the radius using bin search. The right border for search was the sum of all lengths - it must be greater than radius. And I've got WA 14. After changing right border to 10^6 I've got AC. If you try to check a very big radius, the parameter of arcsin gets very low. I assume the function just returns its parameter if it's very close to 0 but your eps needs to be very low as well. Also, the raduis of a polygon's circumscribed circle can be infinitely large no matter what's the upper boundary for its sides is. In this problem, there is a lower boundary too, so you can actually limit your binary search with something. | If you have WA6 or WA3, you have to look on these tests | KOTMAKRUS [SPbPU] | 1052. Охота на зайцев | 17 мар 2017 10:25 | 2 | 6 0 3 0 0 3 0 0 3 1 2 2 1 answer 5 (0 0 is not) 16 15 15 16 17 17 19 18 21 19 23 75 19 16 62 13 69 10 76 7 83 4 90 1 97 -2 104 -5 111 -8 118 -11 125 answer: 10 (last 10) 13 1 1 1 1 1 1 16 62 13 69 10 76 7 83 4 90 1 97 -2 104 -5 111 -8 118 -11 125 answer: 10 (last 10 your program could get 10 in prev test and get 13 here) 8 1 1 1 1 1 1 0 0 0 0 0 0 0 0 2 2 answer 8 5 4 4 4 4 4 4 4 4 4 4 answer 5 I hope, it will help you (P.S. you can click on my nickname and write me, i with big pleasure help you) Edited by author 03.03.2017 22:18 Wrong test cases. No two rabbits are in the same point | if you get WA #21 | notbot | 1346. Интервалы монотонности | 17 мар 2017 09:00 | 1 | I resolved WA21 using this case: 1 5 1 1 2 3 4 Correct Answer => 1 the problem with my solution was initialisation of the slope in case the first 2 elements are equal. | seems there is O(n*log(n)) solution of this problem. | Shen Yang | 1384. Пусти козла в огород 4 | 17 мар 2017 06:35 | 2 | using binary search r, and check for each segment,find the inner side part of other segment that distance is smaller than 2*r,get the segment of these points in each line, check if union of them is the hole line segment. for check two segments' distance we only need to check innerside adjctent two line segments it can be done by O(n*log(n)) sweepline precalculate.. admin please set another version with n<=100000. | to admins | coolhackermasya | 2035. Очередной пробный тур | 16 мар 2017 20:12 | 1 | i wrote code using int (not long) and got AC. Add more tests! | Any hints? | Cebotari Vladislav | 2110. Удалить или максимизировать | 15 мар 2017 19:43 | 7 | I have tried with a greedy algorithm but gives WA#8, any tests pls? Yep, my answer is also 7. Still WA#8 here another tests for my program, can u check pls? 5 3 1245 5553 3112 677 1 answer -> 7609 8 2 12455 6666 3312 245 3432 666 421 444 answer -> 16383 Hard to tell your problem without a code. Greedy algorithm is wrong. Try this: 4 1 16 10 9 6 The answer should be 31 because 16 or 9 or 6 is 31. But the greedy algorithm gives 30. Manciu Ion , yes, for me is 15. For mms: Mine gives 31 too Edited by author 15.03.2017 19:44 | Please help | LuckyD | 1785. Трудности локализации | 15 мар 2017 15:41 | 3 | Why "wrong answer"? a=input() if 0<a<5: print('few') elif 4<a<10: print("sveral") elif 9<a<20: print("pack") elif 19<a<50: print("lots") elif 49<a<100: print('horde') elif 99<a<250: print('throng') elif 249<a<500: print("swarm") elif 499<a<1000: print("zounds") elif 1000<a: print ('legion') | HINT | xalumok | 1048. Сверхдлинные суммы | 15 мар 2017 13:49 | 1 | HINT xalumok 15 мар 2017 13:49 In c++ use scanf, or write this: #define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) And in main func write sync; | Что не так с этим решением? | EveHo | 1197. Один в поле воин | 14 мар 2017 19:33 | 6 | #include <iostream> #include <cstdio> #include <cmath> using namespace std; const int MIN = 1, MAX = 8; int free(int x0, int y0) { int c = 0; double r0 = sqrt(5), r; for (int x = x0 - 2; x <= x0 + 2; x++) for (int y = y0 - 2; y <= y0+2; y++) { r = sqrt(pow(x - x0, 2) + pow(y - y0, 2)); if (r == r0 && x >= MIN && x <= MAX && y >= MIN && y <= MAX) c++; }
return c; } int main() { int T; // kolichestvo testovyx blokov cin >> T; cin.ignore();
int x, y; for (int t = 0; t < T; t++) { x = cin.get() - 'a' + 1; y = cin.get() - '0'; cout << free(x, y) << endl; cin.ignore(); } } Edited by author 20.11.2016 00:44 if (x >= MIN && x <= MAX && y >= MIN && y <= MAX) r = sqrt(pow(x - x0, 2) + pow(y - y0, 2)); if (r == r0) c++; Edited by author 20.11.2016 15:06 А в чем суть изменения, которое вы предлагаете? Тот же самый код в итоге, который дает ошибку в первом тесте, как и исходный. You shouldn't compare floats via strict "==". You should better do integer valuations only: int r0 = 25; int r = (x-x0)*(x-x0) + (y-y0)*(y-y0); if (r == r0...) | Help in understanding the problem | Neeraj Kumar | 1881. Длинное условие задачи | 14 мар 2017 17:07 | 3 | How did the sample output was calculated to be 2? 1st page will have 3 lines : To be or not 2nd page will have only one line: to be Is my understanding correct? | All tests in forum didn't help me :( WA5 | Rocky.B | 1303. Минимальное покрытие | 14 мар 2017 15:26 | 2 | #include <bits/stdc++.h> #define f first #define s second #define pb push_back #define ppb pop_back #define mp make_pair #define pii pair <int, int> #define pll pair <ll, ll> #define ld long double #define ll long long #define ull unsigned ll #define bit(x) __builtin_popcountll(x) #define all(x) x.begin(), x.end() #define sqr(x) ((x) * 1ll * (x)) #define sz(x) (int)x.size() #define purple ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0); #define rep(_i, _from, _to) for (int _i = _from; _i <= _to; _i++) #define per(_i, _from, _to) for (int _i = _from; _i >= _to; _i--) #define nl '\n' #define ioi exit(0); #define _225day "" using namespace std; const int N = 1e6 + 7, mod = 1e9 + 9, inf = 1e9 + 7; const ll linf = (ll)1e18 + 7; const ld eps = 1e-15, pi = 3.141592; const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1}, dy[] = {0, 1, 0, -1, 1, -1, 1, -1}; int n, m, base = 50000; int s[N]; pii a[N]; struct Tree{ int ans, add; } t[N << 2]; inline bool cmp(pii x, pii y){ if (x.f != y.f) return x.f < y.f; } inline bool Check(int pref){ memset(s, 0, sizeof(s)); rep(i, 1, pref) s[a[i].f]++, s[a[i].s + 1]--; rep(i, 0, m + base){ s[i] += s[i - 1]; if (i > base && !s[i]) return 0; } return 1; } inline void Push(int v, int tl, int tr){ if (t[v].add && tl != tr){ t[v + v].add += t[v].add, t[v + v + 1].add += t[v].add; t[v + v].ans += t[v].add, t[v + v + 1].ans += t[v].add; t[v].add = 0; } } inline void Update(int l, int r, int add, int v = 1, int tl = 0, int tr = N){ Push(v, tl, tr); if (l <= tl && tr <= r){ t[v].ans += add; t[v].add += add; return; } if (tl > r || tr < l) return; int tm = tl + tr >> 1; Update(l, r, add, v + v, tl, tm); Update(l, r, add, v + v + 1, tm + 1, tr); t[v].ans = min(t[v + v].ans, t[v + v + 1].ans); } inline int Get(int l, int r, int v = 1, int tl = 0, int tr = N){ Push(v, tl, tr); if (l <= tl && tr <= r) return t[v].ans; if (tl > r || tr < l) return inf; int tm = tl + tr >> 1; return min(Get(l, r, v + v, tl, tm), Get(l, r, v + v + 1, tm + 1, tr)); } int main(){ #ifndef _225day freopen (_225day".in", "r", stdin); freopen (_225day".out", "w", stdout); #endif cin >> m; while (1){ int x, y; cin >> x >> y; if (x == 0 && y == 0) break; a[++n] = {x + base + 1, y + base}; } sort (a + 1, a + 1 + n, cmp); int l = 1, r = n, ans = -1, mid; while (l <= r){ mid = l + r >> 1; if (Check(mid)) ans = mid, r = mid - 1; else l = mid + 1; } if (ans == -1) cout << "No solution", ioi ans = n; rep(i, 1, ans) Update(a[i].f, a[i].s, 1); vector <pii> res; rep(i, 1, ans){ Update(a[i].f, a[i].s, -1); if (!Get(base + 1, m + base)) Update(a[i].f, a[i].s, 1), res.pb({a[i].f, a[i].s}); } sort (all(res), cmp); cout << sz(res) << nl; for (auto i : res) cout << i.f - base - 1 << ' ' << i.s - base << nl; ioi } Same problem :( WA5, WA5, WA5... What causes that? | WA 14 | Sirko | 1185. Wall | 14 мар 2017 03:32 | 3 | WA 14 Sirko 5 янв 2016 23:42 Can anybody give me some hint about test 14? Got AC using Graham's scan. Still can't figure out where's a bug in my previous O(N) solution. If you go throw points clockwise and remove one that creates not clockwise angle. This idea is wrong. Counter test: 8 1 0 0 1 3 3 3 1 1 4 0 2 1 5 3 5 -1 Result is 23 Edited by author 14.03.2017 03:32 Edited by author 14.03.2017 03:32 | WA 18 | coolhackermasya | 1642. Одномерный лабиринт | 13 мар 2017 23:05 | 1 | WA 18 coolhackermasya 13 мар 2017 23:05 | Hints for WA15 | Ade | 1133. Последовательность Фибоначчи | 13 мар 2017 20:16 | 1 | 46 1836311903 -46 -1836311903 45 | It seems that TL is ridiculously strict. | MVM | 2039. Полосатый квадрат | 13 мар 2017 19:12 | 3 | Is it because O(nm log (n + m)) solutions are not supposed to pass or something like that? My solution has relatively high constant, but O(nm(n + m)) or O(nm log^2 (n + m)) solutions probably won't pass even if TL was bigger, I think. Edited by author 29.03.2015 20:20 usigned int +hash get Accept |
|
|