diff options
41 files changed, 1285 insertions, 34 deletions
diff --git a/EveryoneLovesToSleep/main.cpp b/EveryoneLovesToSleep/main.cpp new file mode 100755 index 0000000..e918150 --- /dev/null +++ b/EveryoneLovesToSleep/main.cpp @@ -0,0 +1,110 @@ +#include <bits/stdc++.h> +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +struct Time { + int H; + int M; + + bool operator<(const Time &other) const { + if (H < other.H) { + return true; + } else if (H == other.H) { + if (M < other.M) { + return true; + } else { + return false; + } + } + return false; + } + Time operator-(const Time &other) const { + Time result; + result.H = H - other.H; + result.M = M - other.M; + if (result.M < 0) { + result.M += 60; + } + return result; + } +}; + +void solve() { + int n; + Time bedtime; + cin >> n >> bedtime.H >> bedtime.M; + vector<Time> v(n); + bool flag = false; + for (auto &x : v) { + cin >> x.H >> x.M; + if (x.H == bedtime.H && x.M == bedtime.M) { + flag = true; + } + if (x.H < 12) { + x.H += 23; + } + } + if (flag) { + cout << 0 << ' ' << 0 << '\n'; + return; + } + Time mn = v[0]; + Time mx = {0, 0}; + for (int i = 0; i < n; i++) { + Time cur = v[i]; + cur.H = cur.H % 24; + if (cur < mn) { + mn = v[i]; + } + } + dbg(mn.H, mn.M); + cout << (mn - bedtime).H % 24 << ' ' << (mn - bedtime).M << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/EveryoneLovesToSleep/main_input0.txt b/EveryoneLovesToSleep/main_input0.txt new file mode 100644 index 0000000..baa6cf3 --- /dev/null +++ b/EveryoneLovesToSleep/main_input0.txt @@ -0,0 +1,10 @@ +3 +1 6 13 +8 0 +3 6 0 +12 30 +14 45 +6 0 +2 23 35 +20 15 +10 30 diff --git a/EveryoneLovesToSleep/main_output0.txt b/EveryoneLovesToSleep/main_output0.txt new file mode 100644 index 0000000..1a72a45 --- /dev/null +++ b/EveryoneLovesToSleep/main_output0.txt @@ -0,0 +1,3 @@ +1 47 +0 0 +10 55 diff --git a/codeforces/MakeItUgly/main.cpp b/codeforces/MakeItUgly/main.cpp new file mode 100755 index 0000000..22b800e --- /dev/null +++ b/codeforces/MakeItUgly/main.cpp @@ -0,0 +1,90 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { + int n; + cin >> n; + vi v(n); + for (auto &x : v) { + cin >> x; + } + int cnt_front = 0; + int cnt_back = 0; + for (int i = 0; i < n - 1; i++) { + dbg(v[i + 1], v[i]); + if (v[i + 1] == v[i]) { + cnt_front++; + } else { + break; + } + } + for (int i = n - 1; i >= 0; i--) { + if (v[i - 1] == v[i]) { + cnt_back++; + } else { + break; + } + } + if (cnt_front == n - 1 && cnt_back == n - 1) { + cout << -1 << '\n'; + return; + } + + if (cnt_front == 0 || cnt_back == 0) { + cout << 0 << '\n'; + return; + } + cnt_front++; + cnt_back++; + cout << min(cnt_front, cnt_back) << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/codeforces/MakeItUgly/main_input0.txt b/codeforces/MakeItUgly/main_input0.txt new file mode 100644 index 0000000..72233ee --- /dev/null +++ b/codeforces/MakeItUgly/main_input0.txt @@ -0,0 +1,9 @@ +4 +3 +2 2 2 +5 +1 2 1 2 1 +1 +1 +7 +3 3 3 5 3 3 3 diff --git a/codeforces/MakeItUgly/main_output0.txt b/codeforces/MakeItUgly/main_output0.txt new file mode 100644 index 0000000..97ef938 --- /dev/null +++ b/codeforces/MakeItUgly/main_output0.txt @@ -0,0 +1,4 @@ +-1 +1 +-1 +3 diff --git a/codeforces/TechnicalSupport/main.cpp b/codeforces/TechnicalSupport/main.cpp index 57e8dd3..c9ee12d 100755 --- a/codeforces/TechnicalSupport/main.cpp +++ b/codeforces/TechnicalSupport/main.cpp @@ -1,4 +1,4 @@ -#include<bits/stdc++.h> +#include <bits/stdc++.h> using namespace std; @@ -38,14 +38,14 @@ void solve() { cout << (cnt == 0 ? "Yes" : "No") << '\n'; } -int main () { - ios_base::sync_with_stdio(false); - cin.tie(NULL); - int tt; - cin >> tt; - while(tt--) { +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { solve(); - } + } } /* stuff you should look for: diff --git a/codeforces/UltraFastMathmatician/main.cpp b/codeforces/UltraFastMathmatician/main.cpp index 83ef653..b096db4 100755 --- a/codeforces/UltraFastMathmatician/main.cpp +++ b/codeforces/UltraFastMathmatician/main.cpp @@ -1,15 +1,15 @@ -#include<bits/stdc++.h> +#include <bits/stdc++.h> using namespace std; -int main () { - ios_base::sync_with_stdio(false); - cin.tie(NULL); +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); string s1, s2; cin >> s1 >> s2; - string ans=""; - for(int i = 0; i < s1.size(); i++) { - ans+=((s1[i] - '0') ^ (s2[i] - '0') + '0'); + string ans = ""; + for (int i = 0; i < s1.size(); i++) { + ans += ((s1[i] - '0') ^ (s2[i] - '0') + '0'); } cout << ans << endl; } diff --git a/cses/DynamicProgramming/DiceCombinations/main.cpp b/cses/DynamicProgramming/DiceCombinations/main.cpp new file mode 100755 index 0000000..392bfe7 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main.cpp @@ -0,0 +1,104 @@ +#include <bits/stdc++.h> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ +// 5 +// 1 1 1 1 1 +// 2 1 2 +// 1 2 2 +// 2 1 2 +// 2 2 1 +// 1 1 3 +// 3 1 1 +// 1 3 1 +// 3 2 +// 2 3 +// 4 1 +// 1 4 +// 5 + +// 4 +// 1 1 1 1 +// 2 1 1 +// 1 2 1 +// 3 1 +// 1 1 2 +// 2 2 +// 1 3 +// 4 + +// 3 +// 1 1 1 +// 2 1 +// 1 2 +// 3 + +// 2 +// 1 1 +// 2 + +// 1 +// 1 +// + +// 1 2 4 8 13 +// + +void solve() { + int n; + cin >> n; + ll sum = 0; + vector<ll> dp(n + 1); + dp[0] = 1; + dp[1] = 1; + for (int i = 2; i <= n; i++) { + for (int j = 0; j < min(6, i); j++) { + dp[i] = (dp[i] + dp[i - j - 1]) % mod; + } + } + cout << dp[n] << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + solve(); +} diff --git a/cses/DynamicProgramming/DiceCombinations/main_input0.txt b/cses/DynamicProgramming/DiceCombinations/main_input0.txt new file mode 100644 index 0000000..00750ed --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_input0.txt @@ -0,0 +1 @@ +3 diff --git a/cses/DynamicProgramming/DiceCombinations/main_input1.txt b/cses/DynamicProgramming/DiceCombinations/main_input1.txt new file mode 100644 index 0000000..bf0d87a --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_input1.txt @@ -0,0 +1 @@ +4
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_input2.txt b/cses/DynamicProgramming/DiceCombinations/main_input2.txt new file mode 100644 index 0000000..7813681 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_input2.txt @@ -0,0 +1 @@ +5
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_input3.txt b/cses/DynamicProgramming/DiceCombinations/main_input3.txt new file mode 100644 index 0000000..62f9457 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_input3.txt @@ -0,0 +1 @@ +6
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_input4.txt b/cses/DynamicProgramming/DiceCombinations/main_input4.txt new file mode 100644 index 0000000..c793025 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_input4.txt @@ -0,0 +1 @@ +7
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_output0.txt b/cses/DynamicProgramming/DiceCombinations/main_output0.txt new file mode 100644 index 0000000..b8626c4 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_output0.txt @@ -0,0 +1 @@ +4 diff --git a/cses/DynamicProgramming/DiceCombinations/main_output1.txt b/cses/DynamicProgramming/DiceCombinations/main_output1.txt new file mode 100644 index 0000000..301160a --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_output1.txt @@ -0,0 +1 @@ +8
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_output2.txt b/cses/DynamicProgramming/DiceCombinations/main_output2.txt new file mode 100644 index 0000000..ca7bf83 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_output2.txt @@ -0,0 +1 @@ +13
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_output3.txt b/cses/DynamicProgramming/DiceCombinations/main_output3.txt new file mode 100644 index 0000000..1758ddd --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_output3.txt @@ -0,0 +1 @@ +32
\ No newline at end of file diff --git a/cses/DynamicProgramming/DiceCombinations/main_output4.txt b/cses/DynamicProgramming/DiceCombinations/main_output4.txt new file mode 100644 index 0000000..4e9e288 --- /dev/null +++ b/cses/DynamicProgramming/DiceCombinations/main_output4.txt @@ -0,0 +1 @@ +63
\ No newline at end of file diff --git a/cses/DynamicProgramming/MinimizingCoins/.gdb_history b/cses/DynamicProgramming/MinimizingCoins/.gdb_history new file mode 100644 index 0000000..926ac64 --- /dev/null +++ b/cses/DynamicProgramming/MinimizingCoins/.gdb_history @@ -0,0 +1,92 @@ +b main +start +n +n +n +n +n +n +q +b main +tui enable +n +start +n +n +s +n +n +n +n +n +n +n +n +n +n +s +n +n +n +n +n +n +n +s +n +n +n +n +n +n +n +s +n +n +n +n +n +q +b main +tui enable +start +b rec +c +n +n +n +n +n +n +n +s +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +n +p c[i] +p n - c[i] +n +n +n +n +n +p cache[n] +q diff --git a/cses/DynamicProgramming/MinimizingCoins/main.cpp b/cses/DynamicProgramming/MinimizingCoins/main.cpp new file mode 100755 index 0000000..2235565 --- /dev/null +++ b/cses/DynamicProgramming/MinimizingCoins/main.cpp @@ -0,0 +1,100 @@ +#pragma GCC optimize("O3") +#include <algorithm> +#include <bits/stdc++.h> +#include <climits> +#include <unordered_map> + +using namespace std; + +using ll = long long; +using pii = pair<int, int>; +using vpii = vector<pii>; +using vi = vector<int>; +using vll = vector<long long>; +using mpii = map<int, int>; +using mpll = map<ll, ll>; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +vi c; + +int rec(int n) { + static int sz = n + 1; + static vi cache(n + 1, sz); + if (n == 0) { + cache[0] = 0; + return 0; + } else { + if (cache[n] != sz) { + return cache[n]; + } + int mn = sz; + for (int i = 0; i < c.size(); i++) { + if (n - c[i] >= 0) { + int xx = rec(n - c[i]); + mn = min(mn, 1 + xx); + } + } + cache[n] = mn; + return cache[n]; + } +} + +void solve() { + int n, x; + cin >> n >> x; + c.resize(n); + for (auto &ci : c) { + cin >> ci; + } + vi dp(x + 1, x + 1); + dp[0] = 0; + for (int i = 1; i <= x; i++) { + for (auto ci : c) { + if (i - ci >= 0) { + dp[i] = min(dp[i], 1 + dp[i - ci]); + } + } + } + if (dp[x] == x + 1) { + cout << -1 << '\n'; + } else { + cout << dp[x] << '\n'; + } +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + solve(); +} diff --git a/cses/DynamicProgramming/MinimizingCoins/main.s b/cses/DynamicProgramming/MinimizingCoins/main.s new file mode 100755 index 0000000..4c60a60 --- /dev/null +++ b/cses/DynamicProgramming/MinimizingCoins/main.s @@ -0,0 +1,679 @@ + .file "main.cpp" + .text +#APP + .globl _ZSt21ios_base_library_initv +#NO_APP + .section .text._ZNSt6vectorIiSaIiEED2Ev,"axG",@progbits,_ZNSt6vectorIiSaIiEED5Ev,comdat + .align 2 + .p2align 4 + .weak _ZNSt6vectorIiSaIiEED2Ev + .type _ZNSt6vectorIiSaIiEED2Ev, @function +_ZNSt6vectorIiSaIiEED2Ev: +.LFB10637: + .cfi_startproc + movq (%rdi), %rax + testq %rax, %rax + je .L1 + movq 16(%rdi), %rsi + movq %rax, %rdi + subq %rax, %rsi + jmp _ZdlPvm@PLT + .p2align 4,,10 + .p2align 3 +.L1: + ret + .cfi_endproc +.LFE10637: + .size _ZNSt6vectorIiSaIiEED2Ev, .-_ZNSt6vectorIiSaIiEED2Ev + .weak _ZNSt6vectorIiSaIiEED1Ev + .set _ZNSt6vectorIiSaIiEED1Ev,_ZNSt6vectorIiSaIiEED2Ev + .section .rodata.str1.8,"aMS",@progbits,1 + .align 8 +.LC0: + .string "cannot create std::vector larger than max_size()" + .section .text.unlikely,"ax",@progbits +.LCOLDB1: + .text +.LHOTB1: + .p2align 4 + .globl _Z3reci + .type _Z3reci, @function +_Z3reci: +.LFB9894: + .cfi_startproc + .cfi_personality 0x9b,DW.ref.__gxx_personality_v0 + .cfi_lsda 0x1b,.LLSDA9894 + pushq %r13 + .cfi_def_cfa_offset 16 + .cfi_offset 13, -16 + pushq %r12 + .cfi_def_cfa_offset 24 + .cfi_offset 12, -24 + pushq %rbp + .cfi_def_cfa_offset 32 + .cfi_offset 6, -32 + pushq %rbx + .cfi_def_cfa_offset 40 + .cfi_offset 3, -40 + movl %edi, %ebx + subq $8, %rsp + .cfi_def_cfa_offset 48 + movzbl _ZGVZ3reciE2sz(%rip), %eax + testb %al, %al + je .L47 +.L6: + movzbl _ZGVZ3reciE5cache(%rip), %eax + testb %al, %al + je .L48 +.L9: + movq _ZZ3reciE5cache(%rip), %rax + testl %ebx, %ebx + je .L49 + movslq %ebx, %r12 + movl _ZZ3reciE2sz(%rip), %r13d + salq $2, %r12 + addq %r12, %rax + movl (%rax), %ecx + cmpl %r13d, %ecx + je .L50 + addq $8, %rsp + .cfi_remember_state + .cfi_def_cfa_offset 40 + movl %ecx, %eax + popq %rbx + .cfi_def_cfa_offset 32 + popq %rbp + .cfi_def_cfa_offset 24 + popq %r12 + .cfi_def_cfa_offset 16 + popq %r13 + .cfi_def_cfa_offset 8 + ret + .p2align 4,,10 + .p2align 3 +.L50: + .cfi_restore_state + movq 8+c(%rip), %rsi + movq c(%rip), %rdx + cmpq %rdx, %rsi + je .L19 + xorl %ebp, %ebp +.L23: + movl %ebx, %edi + subl (%rdx,%rbp,4), %edi + js .L20 +.LEHB0: + call _Z3reci +.LEHE0: + movq 8+c(%rip), %rsi + movq c(%rip), %rdx + addl $1, %eax + cmpl %eax, %r13d + cmovg %eax, %r13d +.L20: + movq %rsi, %rax + addq $1, %rbp + subq %rdx, %rax + sarq $2, %rax + cmpq %rax, %rbp + jb .L23 + movq _ZZ3reciE5cache(%rip), %rax + movl %r13d, %ecx + addq %r12, %rax +.L19: + movl %ecx, (%rax) + addq $8, %rsp + .cfi_remember_state + .cfi_def_cfa_offset 40 + movl %ecx, %eax + popq %rbx + .cfi_def_cfa_offset 32 + popq %rbp + .cfi_def_cfa_offset 24 + popq %r12 + .cfi_def_cfa_offset 16 + popq %r13 + .cfi_def_cfa_offset 8 + ret + .p2align 4,,10 + .p2align 3 +.L49: + .cfi_restore_state + movl $0, (%rax) + xorl %ecx, %ecx + addq $8, %rsp + .cfi_remember_state + .cfi_def_cfa_offset 40 + popq %rbx + .cfi_def_cfa_offset 32 + movl %ecx, %eax + popq %rbp + .cfi_def_cfa_offset 24 + popq %r12 + .cfi_def_cfa_offset 16 + popq %r13 + .cfi_def_cfa_offset 8 + ret + .p2align 4,,10 + .p2align 3 +.L48: + .cfi_restore_state + leaq _ZGVZ3reciE5cache(%rip), %r12 + movq %r12, %rdi + call __cxa_guard_acquire@PLT + testl %eax, %eax + je .L9 + leal 1(%rbx), %ebp + movslq %ebp, %rbp + movq %rbp, %rax + shrq $61, %rax + jne .L43 + movq $0, 16+_ZZ3reciE5cache(%rip) + pxor %xmm0, %xmm0 + movaps %xmm0, _ZZ3reciE5cache(%rip) + testq %rbp, %rbp + je .L51 + salq $2, %rbp + movq %rbp, %rdi +.LEHB1: + call _Znwm@PLT +.LEHE1: + leaq (%rax,%rbp), %rdi + movq %rbp, %r9 + leaq -4(%rbp), %rdx + movq %rax, %rcx + movq %rax, _ZZ3reciE5cache(%rip) + movd _ZZ3reciE2sz(%rip), %xmm1 + shrq $2, %r9 + movq %rdi, 16+_ZZ3reciE5cache(%rip) + cmpq $8, %rdx + jbe .L14 + movq %rbp, %r8 + movq %rax, %rdx + pshufd $0, %xmm1, %xmm0 + andq $-16, %r8 + leaq (%r8,%rax), %rsi + andl $16, %r8d + je .L15 + leaq 16(%rax), %rdx + movups %xmm0, (%rax) + cmpq %rsi, %rdx + je .L45 + .p2align 4,,10 + .p2align 3 +.L15: + movups %xmm0, (%rdx) + addq $32, %rdx + movups %xmm0, -16(%rdx) + cmpq %rsi, %rdx + jne .L15 |