Codeforces Round #595 (Div. 3)

A.cpp

#include <iostream>
#include <algorithm>
using namespace std;

int T[200];

int main() {
    ios_base::sync_with_stdio(false);
    int test; cin >> test;
    int N;
    while(cin >> N) {
        bool odd = false, even = false;
        for(int i=0; i<N; i++) {
            cin >> T[i];
            if (T[i]%2 == 0)
                even = true;
            else
                odd = true;
        }
        sort(T, T+N);
        int mindif = 10000;
        for(int i=1; i<N; i++) {
            mindif = min(mindif, T[i] - T[i-1]);
        }
        cout << (mindif > 1 ? 1 : (even+odd)) << endl;
    }
    
}

B.cpp

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int P[201000];
int V[201000];

int main() {
    ios_base::sync_with_stdio(false);
    int test; cin >> test;
    int N;
    while(cin >> N) {
        for(int i=1; i<=N; i++) 
            cin >> P[i];

        memset(V, 0, sizeof V);
        for(int i=1; i<=N; i++) {
            if (V[i] > 0) continue;

            int count = 1;
            int x = P[i];
            while(x != i) {
                count++;
                x = P[x];
            }
            
            V[i] = count;
            x = P[i];
            while(x != i) {
                V[x] = count;
                x = P[x];            
            }
        }
        
        for(int i=1; i<=N; i++) {
            if (i>1) cout << " ";
            cout << V[i];
        }
        cout << endl;
    }
    
}

C.cpp

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

long long T[1000];

int main() {
    ios_base::sync_with_stdio(false);
    long long test; cin >> test;
    long long N;
    while(cin >> N) {
        int count = 0;
        while(N > 0) {
            T[count++] = N%3;
            N/=3;
        }
        
        long long carry = 0;
        long long lastChange = -1;
        for(int i=0; i<count; i++) {
            T[i] = T[i]+carry;
            if (T[i] == 2) {
                T[i]++;
                lastChange = i;
            }

            carry = T[i]/3;
            T[i] %= 3;
        }
        if (carry)
            T[count++] = carry;

        long long answer = 0;
        for(int i=count-1; i>=0; i--) {
            answer *= 3;
            answer += i<lastChange ? 0 : T[i];
        }
        cout << answer << endl;        
    }
    
}

D.cpp

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#define MAX
using namespace std;

struct Seg {
    int index, a, b;
    Seg(int index, int a, int b) : index(index), a(a), b(b) {}
    
    inline bool operator<(const Seg& that) const{
        if (b!=that.b)
            return b>that.b;
        return index<that.index;
    }
};

vector<Seg> A[200200];
vector<Seg> B[200200];
set<Seg> S;
int X[200200];


int main() {
    ios_base::sync_with_stdio(false);
    int N, K;
    while(cin >> N >> K) {
        memset(A, 0, sizeof A);
        memset(B, 0, sizeof B);
        int minn = 100000000;
        int maxx = 0;
        for(int i=0; i<N; i++) {
            int a, b; cin >> a >> b;
            minn = min(minn, a);
            maxx = max(maxx, b);
            A[a].push_back(Seg(i, a, b));
            B[b].push_back(Seg(i, a, b));
        }
        
        int answer = 0;
        for(int i=minn; i<=maxx; i++) {
            for(int j=0; j<A[i].size(); j++)
                S.insert(A[i][j]);

            while(S.size() > K) {
                X[answer++] = S.begin()->index;
                S.erase(S.begin());
            }

            for(int j=0; j<B[i].size(); j++)
                S.erase(B[i][j]);
        }

        cout << answer << endl;
        for(int i=0; i<answer; i++) {
            if (i>0) cout << " ";
            cout << X[i]+1;
        }
        cout << endl;
    }
    
}

E.cpp

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

long long A[200100], B[200100];
long long T1[200100], T2[200100], TX[200100];

int main() {
    ios_base::sync_with_stdio(false);
    long long N, C;
    while(cin >> N >> C) {
        for(int i=0; i<N-1; i++)
            cin >> A[i];
        for(int i=0; i<N-1; i++)
            cin >> B[i];
        
        T1[0] = 0;
        T2[0] = 20000000000ll;
        for(int i=1; i<N; i++) {
            T1[i] = min(T1[i-1]+A[i-1], T2[i-1]+A[i-1]);
            T2[i] = min(T1[i-1]+C+B[i-1], T2[i-1]+B[i-1]);
        }
        
        for(int i=0; i<N; i++) {
            if (i>0) cout << " ";
            cout << min(T1[i], T2[i]);
        }
        cout << endl;
   
    }
    
}