Common BoardTry to think in terms of mathematics, trying to make accurate judgments This test helped me to find my bug. I modified dijkstra algo and added direction array. 9 12 7 3 9 3 9 2 1 2 1 3 4 7 4 1 5 1 4 8 5 8 6 5 2 6 1 8 Answer:0 Edited by author 31.01.2013 17:37 Thanks a lot! I was maintaining an array how[], which was storing how to get at that node (uphill mode or downhill node). But that failed Test case #11. I modified the code such that I start Dijkstra's algorithm at the destination node (Orlov's city) as the source node and Ivan's city as the target node. I actually interchanged source with end. So now I think my how[] array stores how one should get here. And it passed all test cases! Does this work because we have no limitation on how to start, but rather how we end makes more impact on the solution? I cannot derive a formal proof. Any comments are welcome You have to use 2d array to have 2 min costs from s to t with 2 states 0 (up) and 1 (down) (dis[u][0], dis[u][1]), if you just you 1d array and AC, it must be lucky. This is my AC code run in 0.031s: ((const) inf = 1e9, (define) ep = emplace (= push/insert), (define) eb = emplace_back (= push_back), ep and eb both are faster than push and push_back, emplace_front/emplace/emplace_back = push_front/(push/insert)/push_back but faster because it doesn't copy then moves value into array, it pushes directly into array)
#pragma GCC optimize( "Ofast" ) #pragma GCC target( "avx2", "sse4.2", "abm", "bmi", "bmi2", "fma", "mmx", "popcnt", "lzcnt" ) #include <bits/stdc++.h> #define endl '\n' #define inf 1e18 #define int long long #define pii pair <int, int> #define vii vector <pii> #define tiii tuple <int, int, int> #define viii vector <tiii> #define ep emplace #define eb emplace_back using namespace std; const int MaxN = 1e4 + 10; int n, m, s, t, f[MaxN][2]; vii a[MaxN]; priority_queue <tiii, viii, greater <tiii>> pq; signed main() { cin.tie(0) -> sync_with_stdio(0); __builtin_ia32_ldmxcsr ( 40896 );
fill(&f[0][0], &f[0][0] + sizeof(f) / sizeof(f[0][0]), inf);
cin >> n >> m; for (int u, v, i = 1; i <= m; ++i) { cin >> u >> v; a[u].eb(v, 0); a[v].eb(u, 1); } cin >> s >> t;
f[s][0] = f[s][1] = 0; pq.ep(f[s][0], s, 0); pq.ep(f[s][1], s, 1); while (!pq.empty()) { auto [x, u, y] = pq.top(); pq.pop(); if (x > f[u][y]) continue; if (u == t) break; for (auto [v, z] : a[u]) { int w = f[u][y] + (y != z); if (f[v][z] > w) pq.ep(f[v][z] = w, v, z); } }
cout << min(f[t][0], f[t][1]) << endl; } if you have any question, you can ask me :)) I'm native Russian language speaker, but I really cannot understand what is required in the problem: "Поскольку Вадим не любит сладкое, в конце он выберет себе самый маленький по площади кусочек, однако он не хочет, чтобы кто-то это заметил. Для этого современному обер-форшнейдеру нужно подобрать такой способ элегантно разделить торт, чтобы часть, которая достанется ему, была наибольшего размера." He doesn't like sweets, so he takes part of minimal size, but he wants to maximize size at the same time. WTF, where is the logic here, what does author want from us - to find maximin over all cuts, or something else? My program worked correctly on N in 1 to 9, and incorrectly on numbers greater than 9 (error in string concatenation). I kept getting an error on test 2 until I fixed the error. Apparently, in test 2, the input is a number greater than 10. Try this test: in: 11 out: ((((((((((sin(1)+11)sin(1-sin(2))+10)sin(1-sin(2+sin(3)))+9)sin(1-sin(2+sin(3-sin(4))))+8)sin(1-sin(2+sin(3-sin(4+sin(5)))))+7)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6))))))+6)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7)))))))+5)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8))))))))+4)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8+sin(9)))))))))+3)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8+sin(9-sin(10))))))))))+2)sin(1-sin(2+sin(3-sin(4+sin(5-sin(6+sin(7-sin(8+sin(9-sin(10+sin(11)))))))))))+1 I made all my coordinate variables double, so I had a bug when I printed it out :( cout << (int)x << ' ' << int(y) << '\n'; -> fixed my bug I have tested, and 500 kbytes input reads about 20-30 ms in acm.timus.ru system. It equal to ~25 Mbytes/s speed read. Seems there installed HDD disk. There any plan to use fastest SSD disks in server side ? Many problems solutions actually took many times for accessing input/output, not calculating actual algorithm. 12 12 5 3 11 2 8 4 9 1 6 10 7 answer: 34650 in example output. But, following full check test prints 6300. ----- static bool match(int a[], int n, int b[], int m){ if (n != m) return false; if (n == 0 && m == 0) return true;
int i = std::max_element(a, a + n) - a; int j = std::max_element(b, b + m) - b;
return i == j && match(a, i, b, j) && match(a + i + 1, n - i - 1, b + j + 1, m - j - 1); } int main() { int n = 12; int a[] = { 12, 5, 3, 11, 2, 8, 4, 9, 1, 6, 10, 7 }; int b[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; int ans = 0; do{ if (match(a, n, b, n)) ++ ans;
} while (std::next_permutation(b, b + 12) );
printf("ans = %d\n", ans); return 0; }
6 11 1 1 1 2 1 3 3 1 3 2 2 6 2 4 3 5 5 5 5 4 4 6 6 4 Answer: 0 Just prepare the equation as described and solve for c=x, display_sum + k - (entered_sum + x) == (n + 1) * 2; display_sum + k - entered_sum - x = 2 * n + 2; x = -2 * n - 2 + display_sum + k - entered_sum; if x < 0 then Big Bang! If you get WA5, check case, where policeman catch the thief until first tram arrive. I tried many times and I got TLE7, on code with cin cout, and the visual studio compiler. BUT with this input only 5 million numbers. It should not give TLE (I used ios and tie), which is more strange in g++, ABSOLUTELY the same code gives AC, with a time of 0.187, the code is MORE THAN 5 TIMES FASTER! I understand that g++ and visual differ a lot in terms of compiler settings, but to have such a big difference, I'm just shocked. I am very interested to find out why this is happening. Usually visual is faster, it is very interesting to find out which settings and in which cases make the compiler faster. you don't understand what your code does at all try to think more #include <bits/stdc++.h> using namespace std; #define go ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); typedef long long ll; int main() { go int a, b, c, d; cin >> a >> b >> c >> d; while(a < c){ if(a+b > c) break; a += b; c -= d; } cout << max(a, c);
return 0; } Let's assume delta is the difference between the nearest number in our set. Then we can approve delta will decrease by half (at least) in every 2 rounds. So the simulation will be executed at most 2log 10^18 time, it's about 120. k = 1 k = 2^m for some m k = n k = n-1 cases are enough for solve problem :) #include <iostream> #include <vector> using namespace std; int main() { int N = 45; int M; cin >> M; vector <long long> a(N+2); a[0] = 2, a[1] = 2;
for (int i = 0; i < N; i++) { a[i+2] = (a[i+1] + a[i]); }
//Fibonacci sequence
// F0 = 2; // F1 = 2; // Fn = Fn-1 + Fn-2 cout << a[M-1]; return 0; } Problems 2158-2173 from Ural School Programming Contests 2021 and 2022 were added to the Problem set. |
|