oj.uz

Submission #1115881

# Submission time Handle Problem Language Result Execution time Memory
1115881 2024-11-21T03:19:46 Z Iwantbemaster Cooking (innopolis2018_final_B) C++17
100 / 100
 1 ms 504 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ff first
#define ss second
#define tobit(n) bitset<128>(n)
#define all(v) (v).begin(), (v).end() 
#define rtt(v) rotate(vec.begin(), vec.begin() + k, vec.end()); //move k elements back
int dx[] = {1,0,-1,0,1,1,-1,-1}; int dy[] = {0,1,0,-1,1,-1,1,-1};
const int MOD = 1000000007;
const int MAXN = 2005;
int binpownm(int n, int m){
    if(m <= 1) return n;
    if(m % 2 == 0){
        int t = binpownm(n, m / 2); return t * t;
    } else return binpownm(n, m - 1) * n;
}
string tobin(int n){
    if(n == numeric_limits<int>::min()) return "-1" + string(numeric_limits<int>::digits, '0');
    string res;
    res.reserve(numeric_limits<int>::digits + 1);
    bool cur = (n < 0);
    if(cur) n = -n;
    do { res += char('0' + n % 2); n = n / 2; } while (n > 0);
    if(cur) res += '-';
    return string(res.crbegin(), res.crend());
}
void merge(vector<int>& v, int l, int m, int r){
    vector<int> result; 
    int i = l, j = m + 1;
    while(i <= m && j <= r){
        if(v[i] <= v[j]) result.emplace_back(v[i]), i++;
        else result.emplace_back(v[j]), j++;
    } while(i <= m){
        result.emplace_back(v[i]); i++;
    } while(j <= r){
        result.emplace_back(v[j]); j++; 
    } for(int i = l; i <= r; i++) v[i] = result[i - l];
}
void mergeSORT(vector<int>& v, int l, int r){
    if(l < r){
        int m = (l + r) / 2;
        mergeSORT(v, l, m);
        mergeSORT(v, m + 1, r);
        merge(v, l, m, r);
    }
}
// Алгоритм Манакера || "Короче строка s и мы хотим найти в ней все подпалиндромы" //
vector<int> manacher_odd(string s){ //для нечетных размеров палиндромов
    vector<int> v(s.size(), 1);
    int l = 0, r = 0;
    for(int i = 1; i < s.size(); i++){
        if(i < r) v[i] = min(r - i + 1, v[l + r - i]);
        while(i - v[i] >= 0 && i + v[i] < s.size() && s[i - v[i]] == s[i + v[i]]) v[i]++;
        if(i + v[i] - 1 > r) l = i - v[i] + 1, r = i + v[i] - 1;
    } return v;
}
// Алгоритм Манакера || "Короче строка s и мы хотим найти в ней все подпалиндромы" //
vector<int> manacher_even(string s){ //для четного размеров палиндромов
    vector<int> v(s.size(), 0);
    int l = -1, r = -1;
    for(int i = 0; i < s.size() - 1; i++){
        if(i < r) v[i] = min(r - i, v[l + r - i - 1]);
        while (i - v[i] >= 0 && i + v[i] + 1 < s.size() && s[i - v[i]] == s[i + v[i] + 1]) v[i]++;
        if(i + v[i] > r) l = i - v[i] + 1, r = i + v[i];
    } return v;
}
// PRIMERNO kak pref function no on ishet maksimalnye stroki //
vector<int> z_func(string s){
    vector<int> z(s.size());
    z[0] = 0;
    int l = 0, r = 0;
    for(int i = 1; i < s.size(); i++){
        if(i <= r){
            z[i] = min(z[i - l], r - i + 1);
        }
        while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]]){
            z[i] += 1;
        }
        if(i + z[i] - 1 > r){
            l = i;
            r = i + z[i] - 1;
        }
    } return z;
}
int BIN(vector<int> v, int l, int r, int x){
    if(r >= l){
        int m = l + (r - l) / 2;
        if(v[m] == x) return m;
        if(v[m] > x) return BIN(v, l, m - 1, x);
        return BIN(v, m + 1, r, x);
    } return -1;
}
// PREFIX FUNC p[i] = kolichestvo kakoihto sufix p[i] ravnyy prefu // 
vector<int> p_func(string s){
    vector<int> p(s.size(), 0);
    for(int i = 1; i < s.size(); i++){
        int cur = p[i - 1];
        while(s[i] != s[cur] && cur > 0) cur = p[cur - 1];
        if(s[i] == s[cur]) p[i] = cur + 1;
    } return p;
}
// check to find element in 2D array //
vector<int> FIND2D(vector<vector<int>>& v, int k){
    for(int i = 0; i < v.size(); i++){
        vector<int> cur;
        for(int j = 0; j < v[i].size(); j++){
            cur.emplace_back(v[i][j]);
        }
        int res = BIN(cur, 0, cur.size() - 1, k);
        vector<int> qwe;
        qwe.emplace_back(i);
        qwe.emplace_back(res);
        if(res != -1) return qwe;
    }
    vector<int> qwe = {-1};
    return qwe;
}
int lis(vector<int>& arr) {
    int n = arr.size();
    vector<int> lis(n, 1);
    for(int i = 1; i < n; i++){
        for(int prev = 0; prev < i; prev++){
            if(arr[i] > arr[prev] && lis[i] < lis[prev] + 1){
                lis[i] = lis[prev] + 1;
            }
        }
    } return *max_element(lis.begin(), lis.end());
}
vector<vector<int>> build_prefix_sums_2d(const vector<vector<int>>& a){
    int n = a.size();
    int m = a[0].size();
    vector<vector<int>> prefix_sum(n + 1 , vector<int>(m + 1, 0));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            prefix_sum [i + 1][ j + 1] = prefix_sum[i][j + 1] + prefix_sum[i + 1][j] - prefix_sum[i][j] + a[i][j];
        }
    } return prefix_sum;
}
int findGCD(vector<int> arr, int n){
    int result = arr[0];
    for(int i = 1; i < n; i++) result = __gcd(arr[i], result);
    return result;
}
bool isPrime(int n){
    if(n <= 1) return false;
    if(n <= 3) return true;
    if(n % 2 == 0 || n % 3 == 0) return false; 
    for(int i = 5; i * i <= n; i += 6){
        if(n % i == 0 || n % (i + 2) == 0) return false;
    } return true;
}
vector<vector<int>> g; vector<int> vis;
void dfs(int c){
    vis[c] = true;
    for(auto to : g[c]){
        if(vis[to]) continue;
        dfs(to);
    }
}
int n, p[MAXN];
vector<int> ans;
void FUNC(int x){
    x = n - x;
    rotate(p, p + n - x, p + n);
    reverse(p, p + x);
    ans.push_back(x);
}
void solve(){
    int cur = (n / 2) * 2;
    bool rev = 0;
    while(cur >= 2){
        int x, y;
        if(cur == n) x = 0, y = 1;
        else{
            x = p[cur]; y = p[n - 1];
            if(!rev) x--, y++;
            else x++, y--;
        } x = (x + n) % n; y = (y + n) % n;
        int px = find(p, p + n, x) - p;
        FUNC(px + 1); FUNC(0); FUNC(cur);
        int py = find(p, p + n, y) - p; FUNC(py);
        int pxx = find(p, p + n, x) - p; FUNC(pxx + 1);
        rev ^= 1; cur -= 2;
    } if(n > 1){
        int pos = find(p, p + n, 0) - p;
        if(p[(pos + 1) % n] == n - 1) FUNC(0);
        pos = find(p, p + n, 0) - p;
        FUNC(pos); FUNC(n - pos); FUNC(0);
    }
}
signed main(){
    long long K, D, T, N, L, Ans; cin >> K >> D >> T; T <<= 1;
    N = (K + D - 1) / D;
    // cout << N << endl;
    L = N*D + K;
    Ans += N*D * (T/L);
    T %= L;
    if(T <= K*2) Ans += T/2;
    else { Ans += T-K; T = 0; }
    cout << Ans << "." << ((T&1) ? "5" : "0") << endl;
}
const int fastIO = [](){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    return 0;   
}();

Compilation message

B.cpp: In function 'std::vector<long long int> manacher_odd(std::string)':
B.cpp:52:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
B.cpp:54:41: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         while(i - v[i] >= 0 && i + v[i] < s.size() && s[i - v[i]] == s[i + v[i]]) v[i]++;
      |                                ~~~~~~~~~^~~~~~~~~~
B.cpp: In function 'std::vector<long long int> manacher_even(std::string)':
B.cpp:62:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |     for(int i = 0; i < s.size() - 1; i++){
      |                    ~~^~~~~~~~~~~~~~
B.cpp:64:46: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         while (i - v[i] >= 0 && i + v[i] + 1 < s.size() && s[i - v[i]] == s[i + v[i] + 1]) v[i]++;
      |                                 ~~~~~~~~~~~~~^~~~~~~~~~
B.cpp: In function 'std::vector<long long int> z_func(std::string)':
B.cpp:73:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
B.cpp:77:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |         while(i + z[i] < s.size() && s[z[i]] == s[i + z[i]]){
      |               ~~~~~~~~~^~~~~~~~~~
B.cpp: In function 'std::vector<long long int> p_func(std::string)':
B.cpp:97:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 1; i < s.size(); i++){
      |                    ~~^~~~~~~~~~
B.cpp: In function 'std::vector<long long int> FIND2D(std::vector<std::vector<long long int> >&, long long int)':
B.cpp:105:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
B.cpp:107:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  107 |         for(int j = 0; j < v[i].size(); j++){
      |                        ~~^~~~~~~~~~~~~
B.cpp: In function 'int main()':
B.cpp:197:9: warning: 'Ans' is used uninitialized in this function [-Wuninitialized]
  197 |     Ans += N*D * (T/L);
      |     ~~~~^~~~~~~~~~~~~~

Subtask #1
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 464 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 1 ms 336 KB Output is correct
22 Correct 1 ms 336 KB Output is correct
23 Correct 1 ms 336 KB Output is correct
24 Correct 1 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 336 KB Output is correct
27 Correct 1 ms 464 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 1 ms 336 KB Output is correct
30 Correct 1 ms 336 KB Output is correct
31 Correct 1 ms 336 KB Output is correct
32 Correct 1 ms 348 KB Output is correct
33 Correct 1 ms 336 KB Output is correct
34 Correct 1 ms 336 KB Output is correct
35 Correct 1 ms 336 KB Output is correct
36 Correct 1 ms 336 KB Output is correct
37 Correct 1 ms 336 KB Output is correct
38 Correct 1 ms 336 KB Output is correct
39 Correct 1 ms 336 KB Output is correct
40 Correct 1 ms 504 KB Output is correct
41 Correct 1 ms 432 KB Output is correct
42 Correct 1 ms 504 KB Output is correct
43 Correct 1 ms 336 KB Output is correct
44 Correct 1 ms 336 KB Output is correct
45 Correct 1 ms 336 KB Output is correct
46 Correct 1 ms 336 KB Output is correct
47 Correct 1 ms 336 KB Output is correct
48 Correct 1 ms 336 KB Output is correct
49 Correct 1 ms 336 KB Output is correct
50 Correct 1 ms 504 KB Output is correct
51 Correct 1 ms 336 KB Output is correct
52 Correct 1 ms 336 KB Output is correct
53 Correct 1 ms 336 KB Output is correct
54 Correct 1 ms 336 KB Output is correct
55 Correct 1 ms 336 KB Output is correct