oj.uz

Submission #202652

# Submission time Handle Problem Language Result Execution time Memory
202652 2020-02-17T15:06:25 Z SorahISA Sob (COCI19_sob) C++14
39 / 110
 56 ms 12396 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define double long double

#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

const int maxn = 1 << 20;

vector<int> v(maxn);

int32_t main() {
    fastIO();
    
    int n, m, tok = 0;
    cin >> n >> m;
    
    /// for subtask 1 : n == 2^k ///
    
    if ((1 << __lg(n)) == n) {
        for (int i = m+n-1; i >= m; --i) {
            if (((n-1) & i) == (n-1)) {tok = i+1-n; break;}
        }
        
        for (int i = 0; i < n; ++i) {
            cout << i << " " << (tok+i < m ? tok+i+n : tok+i) << "\n";
        }
        
        return 0;
    }
    
    /// for subtask 2 : n+m == 2^k ///
    
    int now = 1, p;
    for (int i = 1; i < n; ++i) {
        now = (now ? now - 1 : i - 1);
        p = now;
        while (v[now]) {
            swap(v[now], v[p]);
            p += (1 << (int)__lg(v[now]) + 1);
        }
        v[now] = i;
    }
    
    vector<pair<int, int>> ans;
    for (int i = 0; i < n; ++i) ans.push_back({v[i], n+m-i-1});
    sort(ans.begin(), ans.end());
    
    for (auto [L, R] : ans) cout << L << " " << R << "\n";
    
    return 0;
}

Compilation message

sob.cpp: In function 'int32_t main()':
sob.cpp:41:42: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
             p += (1 << (int)__lg(v[now]) + 1);
                        ~~~~~~~~~~~~~~~~~~^~~
sob.cpp:50:15: warning: decomposition declaration only available with -std=c++1z or -std=gnu++1z
     for (auto [L, R] : ans) cout << L << " " << R << "\n";
               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 9 ms 8568 KB Output is correct
3 Correct 10 ms 8568 KB Output is correct
4 Correct 53 ms 12152 KB Output is correct

Subtask #2
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8696 KB Output is correct
2 Correct 10 ms 8568 KB Output is correct
3 Correct 9 ms 8568 KB Output is correct
4 Correct 11 ms 8568 KB Output is correct
5 Correct 9 ms 8568 KB Output is correct
6 Correct 56 ms 12152 KB Output is correct
7 Correct 54 ms 12396 KB Output is correct

Subtask #3
0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 8568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 8568 KB Output is correct
2 Correct 9 ms 8568 KB Output is correct
3 Correct 10 ms 8568 KB Output is correct
4 Correct 53 ms 12152 KB Output is correct
5 Correct 10 ms 8696 KB Output is correct
6 Correct 10 ms 8568 KB Output is correct
7 Correct 9 ms 8568 KB Output is correct
8 Correct 11 ms 8568 KB Output is correct
9 Correct 9 ms 8568 KB Output is correct
10 Correct 56 ms 12152 KB Output is correct
11 Correct 54 ms 12396 KB Output is correct
12 Incorrect 10 ms 8568 KB Output isn't correct
13 Halted 0 ms 0 KB -