Talk is Cheap, Show Me the Code!

0%

AtCoder 185

Posted on In

A - ABC Preparation
The number of tests that can be formed.

abc-prep.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

int main(){
    int a1, a2, a3, a4;
    cin>>a1>>a2>>a3>>a4;
    cout <<min(min(a1,a2), min(a3, a4));
    return 0;
}

B - Smartphone Addiction
Print if the phone battery is able to sustain till getting home.

smartphone-addict.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

int main(){
    int N, m, t;
    cin>>N>>m>>t;
    int n = N;
    int a, b;
    int pre = 0;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        n -= (a - pre);
        if(n<=0) {cout<<"No"<<endl;  return 0;}
        n += (b-a);
        n = min(n, N);
        pre = b;
    }
    n -= (t - pre);
    if (n <= 0) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

C - Duodecim Ferra
The number of ways to divide L into 12 integer-segments.

duodecim-ferra.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

typedef long long LL;

int main(){
    LL n;
    cin>>n;
    LL res = 1;
    for(int i=1;i<=11;i++){
        res = res * (n - i) / i;
    }
    cout<<res<<endl;
    return 0;
}

D - Stamp
Minimum number of moves to stamp an array with stamp of size k.

stamp.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

const int M = 2e5 + 10;
int a[M];
int main(){
    int n, m;
    int res = 0;
    cin>>n>>m;
    for(int i=0;i<m;i++) scanf("%d", &a[i]);
    sort(a, a+m);

    int k = n;
    int pre = 0;
    for(int i=0;i<m;i++){
        int t = a[i] - pre - 1;
        if (t > 0)
            k = min(k, a[i] - pre - 1);
        pre = a[i];
        a[i] = t;
    }
    a[m] = n - pre ;
    for(int i=0;i<=m;i++){
        if(a[i] % k==0) res += a[i] / k ;
        else res += a[i] / k  + 1;
    }
    cout<<res<<endl;
    return 0;
}

E - Sequence Matchinge
Minimum x+y given two sequence A, B of length n, m respectively.
x: removals from A and B to make them of equal length.
y: number of elements where A_i is not equal to B_i;

seq-match.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

const int N = 10010;
int a[N], b[N];
int f[N][N];

int main(){
    int n, m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) f[i][j] = max(n, m);
    for(int i=1;i<=n;i++) f[i][0] = i;
    for(int j=1;j<=m;j++) f[0][j] = j;
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
    for(int j=1;j<=m;j++) scanf("%d", &b[j]);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            f[i][j] = min(f[i][j], f[i-1][j] + 1);
            f[i][j] = min(f[i][j], f[i][j-1] + 1);
            if(a[i]!=b[j]) f[i][j] = min(f[i][j], f[i-1][j-1] + 1);
            else f[i][j] = min(f[i][j], f[i-1][j-1] );
        }
    cout<<f[n][m]<<endl;
    return 0;
}

F - Range Xor Query
Range query for the Xor operation.
Use fenwick-tree to solve.

range-xor-query.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <set>
using namespace std;

const int N = 300010;
int s[N], a[N];
int n;

int lowbit(int x){
    return x & -x;
}

void modify(int x, int v){
    for(int i=x;i<=n;i+=lowbit(i)){
        s[i] ^= v;
    }
}

int sum(int x){
    int res = 0;
    for(int i=x;i;i-=lowbit(i)){
        res ^= s[i];
    }
    return res;
}

int main(){
    int q;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d", &x);
        a[i] = a[i-1] ^ x;
    }
    for(int i=1;i<=n;i++) {
        s[i] = a[i] ^ a[i-lowbit(i)];
    }

    while(q--){
        int t, x, v;
        scanf("%d%d%d", &t, &x, &v);
        if(t==1) modify(x, v);
        else printf("%d\n", sum(v) ^ sum(x-1));
    }
    return 0;
}