Common BoardI'll just combine two previous hints. Use bubble sort and THEN use random. Use bubble sort and THEN assert that the balls are the same color in (n / 2) and (n / 2 + 1) Hi, I'm still getting WA-1, can anybody give me answers to these tests: 80 60 60 80 60 60 Thanks. My AC program writes following answers: 80 60 >> 199 60 80 >> 200 60 60 >> 160 BTW I solved this problem without any boring special cases consideration, using only stupid DP[101][101]... My any Java solutions get's WA 1 too. i think it's problem with java, have same too. wa for any solution, which has got ac before. I saw DP[101][101], is it for dynamic programming ? I don't think we'll need it. Edited by author 31.10.2011 02:12 in this problem dont need DP. you may take max from two optimal cases ;D ...or think how to make on DP Edited by author 31.10.2011 02:21 80 60 199 60 80 200 60 60 160 Its quite easy to do. Basically, there are 2 "worst" cases: 1). We take 40 right (equals 40*2=80 secs), then throw all the rest of the right ones (2*(b-40) secs), and them take the 40 left (40 secs). The time is 80+2*(b-40)+40=120+2*(b-40). 2). We take 39 left (78 secs), take 40 left ones (40 secs), throw all the other left ones away (2*(a-40)), and take the last right one (1 sec). The time is 78+40+2*(a-40)+1=119+2*(a-40). The answer is the maximum of these two. ONU_1785 In the case two, when you say: "We take 39 left (78 secs)", why? If I take the first 39 lefts, this not is 39 secs???? one second per each slipper ONU_1785 means 39 right, it's just a typo. Edited by author 20.05.2012 15:54 In the case two, when you say: "We take 39 left (78 secs)", why? If I take the first 39 lefts, this not is 39 secs???? one second per each slipper He wanted to wright 'We take 39 right' Very hard problem, I thought about 20 minutes and then wrote DP[101][101][41][41] :) why 39 rights and no 40? There are 2 possible bad ways: 1) mode "putting on left slippers" |*0*|0| slippers come only for right legs |*0*|40| (time +40*2) if there are more than 40 slippers for right legs they still come |*0*|40| (time + (b-40)*2) then there are slippers only for left legs |*40*|40| (time +40); 2) mode "putting on left slippers" |*0*|0| slippers come for right legs except 1 |*0*|39| (time +39*2) then slippers come only for left legs |*40*|39| (time +40)
now mode changes to "putting on right slippers" |40|*39*| happy centipede hopes to get the last needed right slipper, she gets all slippers for left legs, which are still left |40|*39*| (time + (a-40)*2) and finally she gets the last one right slipper |40|*40*| (time +1) So, just choose the worst way according to exact input. you have 60 and 80, from where you take 39? a-b and c-d are close, but not touching each other. -2 0 0 -1 0 0 0 1 0 0 1000000 1 In this test all numbers are big (~1e9), so it can be precision errors/overflow. You should use NTT with big modulo to avoid doubles The width of the last column of ranklist, "Last AC", is a little narrower than needed. The ranklist table always displayes abnormal. Please can you take a look? And so does the bottom ranklist table in the author page. Solved the problem using segment tree. Im using VC++ 12 and it's giving the correct answer for the sample. Still while sending (VC++ 2010) im getting WA 1. Changing it to G++ C++ 11 gives AC. What's the difference and why am i getting WA 1 when i choose VC++? Code: #include <iostream> #include <vector> using namespace std; const int MAXN=100000; pair<int, int> t[4*MAXN]; int z=1; void build_tree(int v, int tl, int tr) { if (tl==tr) { t[v]=make_pair(1,z++); return; } int tm=(tl+tr)/2; build_tree(2*v, tl, tm); build_tree(2*v+1, tm+1, tr); t[v].first=t[2*v].first+t[2*v+1].first; t[v].second=-1; } int req(int v, int tl, int tr, int n) { if (tl==tr) { --t[v].first; return t[v].second; } int tm=(tl+tr)/2; t[v].first--; if (t[2*v].first>=n) req(2*v, tl, tm, n); else req(2*v+1, tm+1,tr,n-t[2*v].first); } int main() { int n, k; cin>>n>>k; build_tree(1,1,100000); int cur=k; for (int i=0; i<n; ++i) { int h=req(1,1,100000, cur); cout<<h<<" "; if (i==n-1) break; cur=(cur-1+k)%(n-1-i); if (cur==0) cur+=n-1-i; } } Edited by author 10.03.2013 07:20 Not sure, but it could be because of this t[4*MAXN] instead of t[400000] He donated all the money to the poor and went to bed with a clear conscience... Yeah, he correctly thought that people will forgive him, because it is charity WpKRwvgKenn output shold be "WpKRwvgKenneKgvwRKpW" not "WpKRwvgKennneKgvwRKpW" Этот код работает везде, кроме как на этом сайте Runtime error test 1. Почему??? import sys array4 = dict() result = "" for i in sys.stdin.read().split("\n")[1:]: array4[str(i.split(" ")[0])] = str(i.split(" ")[1]) def QSort(arr3): if len(arr3) < 2: return arr3 else: privot, do3, sered, posle = int(arr3[list(arr3.keys())[0]]), dict(), dict(), dict() for x, i in arr3.items(): if int(i) > privot: do3[x] = i elif int(i) < privot: posle[x] = i else: sered[x] = i return {**QSort(do3), **sered, **QSort(posle)} for t, y in QSort(array4).items(): result += f"{t} {y}\n" print(result.strip('\n')) # include <bits/stdc++.h> using namespace std; using ll = long long; #define vec vector #define int long long #define ld long double #define f first #define s second #define pb push_back #define fe(x, a) for (auto& x : a) #define pw(x) (1ll << x) #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() using pii = pair<int, int>; const int mod = 1e9 + 7; const ll OO = 1e16; const int N = 1e5 + 2; const ld eps = 1e-3; template<typename T> bool umn(T &a, T b) { return a > b ? (a = b, 1) : 0; } template<typename T> bool umx(T &a, T b) { return a < b ? (a = b, 1) : 0; } void solve() { int n, best = -1, ans = 0; cin >> n; set<pii> setik; for (int i = 0, x; i < n + 1; ++i) { x = -OO; if (i < n) cin >> x; if (i && x < (*setik.begin()).f) if (umx(best, i - (*setik.begin()).s - !(*setik.begin()).s)) ans = (*setik.begin()).s; setik.insert({x, i}); } cout << ans + 1; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; // cin >> t; while (t--) solve(); } Input: 9 16372 24788 000010111 001111101 010010001 010011001 111100101 010100100 110011000 100000000 111110000 Possible answer (a's should be the same, d's can differ in you answer): 163720 000000000 000000d0d 0000d000d 0000dd00d 00dd00d0d 000d00d00 0d00dd000 000000000 0dddd0000 Matrix for the graph in the answer: 000010111 001111000 010000000 010000000 110000000 010000000 100000000 100000000 100000000 Edited by author 12.05.2023 13:49 Use this site to visualise the graph using matrix and firstly change enumeration from 1,2,3... to 0,1,2... : https://graphonline.ru/# Edited by author 12.05.2023 13:55 Edited by author 12.05.2023 13:55If you have a mistake, most likely you delete connections of the input graph in a wrong way. And most likely, because you search the connected components incorrectly. If you are solving using formula, there are some corner cases. IN 0 0 0 0 OUT 0 IN 17 0 0 17 OUT 17 And just some random test. IN 7 9 6 8 OUT 15.165177459575631 Who can tell me………… Why got WA#12? if you have to cut a word, the word must end with string1+string2 (without '-'). Therefore I used: String h=word.toUpperCase(); String s=(string1+string2).toUpperCase(); if (h.endsWith(s)){ int z=h.lastIndexOf(s) //<-- !!! ... This helped me (in Java) to avoid WA#12. Following test helped me to pass test #12: 0 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa.aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. #include <iostream> int main() { long long int y1; int y2, y3, y4; std::cin; std::cin >> y1; y4 = y1 / 16777216; y1 = y1 % 16777216; y3 = y1 / 65536; y1 = y1 % 65536; y2 = y1 / 256; y1 = y1 % 256; y1 = y1 * 16777216 + y2 * 65536 + y3 * 256 + y4; std::cout << y1; return 0; } в данном коде есть проблема: в данном компиляторе первый cin ничего не делает и второй получает на вход строку. La testoj estis kreitaj uzante hazardigilon en programo kiu ricevis AC: 12 10 8 -> 21 3 12 15 13 -> 36 3 10 18 12 -> 31 3 10 9 8 -> 21 3 20 6 16 -> 45 12 7 7 7 -> 18 3 13 15 1 -> 0 0 18 19 4 -> 9 3 18 19 19 -> 54 3 0 1 13 -> 12 12 7 10 7 -> 18 3 6 2 16 -> 27 16 2 5 10 -> 13 7 19 18 14 -> 39 3 18 3 14 -> 42 13 19 7 2 -> 6 3 0 8 2 -> 1 0 10 13 16 -> 35 5 7 9 11 -> 24 4 16 8 14 -> 39 8 7 10 7 -> 18 3 4 2 12 -> 19 12 11 15 1 -> 0 0 5 20 1 -> 0 0 8 13 8 -> 21 3 18 2 19 -> 54 19 2 12 20 -> 23 10 5 10 16 -> 25 8 10 1 3 -> 9 4 17 12 2 -> 6 3 2 7 3 -> 6 0 14 19 19 -> 46 3 3 0 5 -> 11 7 6 7 12 -> 23 7 14 11 7 -> 18 3 11 3 6 -> 18 5 2 11 10 -> 13 1 17 5 11 -> 33 8 10 16 12 -> 31 3 7 19 15 -> 28 3 17 15 5 -> 12 3 19 5 12 -> 36 9 4 12 6 -> 13 0 6 9 17 -> 28 10 4 4 18 -> 25 16 16 3 17 -> 48 16 13 0 2 -> 6 4 8 18 9 -> 24 0 3 19 8 -> 13 0 17 16 9 -> 24 3 11 5 6 -> 18 3 20 3 8 -> 24 7 1 9 13 -> 14 5 16 2 10 -> 30 10 15 2 2 -> 6 3 6 1 15 -> 26 16 5 14 19 -> 28 7 18 10 1 -> 3 3 20 1 2 -> 6 3 1 5 5 -> 6 1 3 3 12 -> 17 11 10 5 17 -> 36 14 8 19 7 -> 18 0 3 5 8 -> 13 5 18 8 15 -> 42 9 20 14 3 -> 9 3 4 0 16 -> 24 18 15 3 5 -> 15 4 7 4 9 -> 22 7 7 14 20 -> 33 8 8 10 3 -> 6 1 16 0 1 -> 3 3 13 2 3 -> 9 3 8 2 19 -> 34 19 6 7 10 -> 21 5 20 6 6 -> 18 3 11 7 1 -> 3 3 17 16 15 -> 42 3 5 11 2 -> 3 0 20 9 3 -> 9 3 8 2 4 -> 12 4 6 13 6 -> 15 0 12 1 3 -> 9 4 1 8 15 -> 16 8 10 17 16 -> 35 3 9 0 15 -> 33 17 4 2 18 -> 25 18 8 10 6 -> 15 3 12 0 13 -> 37 15 20 5 20 -> 57 17 4 14 20 -> 27 8 4 1 16 -> 23 17 17 13 6 -> 15 3 18 8 12 -> 33 6 20 3 3 -> 9 3 16 19 6 -> 15 3 0 13 14 -> 13 1 3 4 18 -> 23 16 4 10 15 -> 22 7 2 14 7 -> 10 0 Eraroj en testoj pruvas la neperfektecon de la tasko For me from statement was clear, that there are always solutions, either one or multiple. But in test 5 there is no solution. You have to print IMPOSSIBLE in this case. Anti-hash testcases are added, so I guess intended solution isn't hashing. However I can't think of any. My code was failing WA#3 until I got this case working: 4 3 1 1 1 14 1 1 3 1 2 3 2 2 3 2 4 3 3 4 3 4 4 3 2 3 3 1 1 1 1 2 1 2 2 1 1 4 1 2 4 1 3 4 1 3 3 1 > 11000000111111 Other: 8 0 0 1 1 0 0 1 1 35 1 2 1 1 1 1 1 3 1 2 3 1 1 6 1 2 5 1 5 6 1 5 5 1 6 6 1 3 4 1 3 3 1 4 4 1 4 7 1 4 6 1 5 7 1 1 2 0 1 1 0 1 3 0 2 3 0 1 6 0 2 5 0 5 6 0 5 5 0 6 6 0 3 4 0 3 3 0 4 4 0 4 7 0 4 6 0 5 7 0 1 7 2 1 2 2 1 1 2 3 3 2 5 5 2 > 00111100011111111111111100011100000 9 1 1 9 9 1 9 9 1 1 70 1 9 9 1 9 1 1 9 5 1 1 1 2 2 1 3 3 9 4 4 9 5 5 1 6 6 9 7 7 9 8 8 1 9 9 1 1 1 9 2 2 9 3 3 1 4 4 1 5 5 9 6 6 1 7 7 1 8 8 9 9 9 9 1 2 1 2 3 1 3 4 1 4 5 1 5 6 1 6 7 1 7 8 1 8 9 1 1 2 9 2 3 9 3 4 9 4 5 9 5 6 9 6 7 9 7 8 9 8 9 9 1 3 9 1 4 9 1 5 9 1 6 9 1 7 9 1 8 9 1 9 9 3 4 1 2 4 1 3 5 1 2 5 1 3 4 9 2 4 9 3 5 9 2 5 9 1 1 5 1 2 5 1 3 5 2 2 5 3 3 5 8 9 5 7 9 5 9 9 5 6 6 5 3 3 1 3 4 1 3 5 1 4 5 1 5 5 1 5 6 1 5 7 1 6 7 1 7 7 1 > 1101111111110000000001101101101111110111111101111111000000000001111100 7 1 1 1 3 1 1 1 11 4 4 3 3 4 3 4 5 3 3 5 3 1 3 3 5 8 3 3 3 3 5 5 3 4 4 1 1 7 3 1 7 1 > 11110000011 |
|