COFO::Round #649 ( div 2 )

Problem A : XXXXX

Point

Design(x)

Big O(time)

Code(x)

#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define pb(x) push_back(x)
#define f first
#define s second
#define endl '\n'
typedef  long long ll;
const int MAXN = 100000 + 10;
using namespace std;

ll n, x;
ll a[MAXN];
ll psum[MAXN], rpsum[MAXN];
void process(){
    rep(i, 0, MAXN) a[i] = psum[i] = rpsum[i] = 0;
    int ans = 0;
    cin >> n >> x;
    rep(i, 0, n) cin >> a[i];
    psum[0] = a[0], rpsum[n-1] = a[n-1];
    int len = ((psum[0] % x) != 0 ? 1 : 0);
    rep(i, 1, n){
        psum[i] = psum[i-1] + a[i];
        if((psum[i] % x) != 0) len = i+1;
    }
    ans = max(ans, len);
    len = ((rpsum[n-1] % x) != 0 ? 1 : 0);
    r_rep(i, n-2, -1){
        rpsum[i] = rpsum[i+1] + a[i];
        if((rpsum[i] % x) != 0) len = n-i;
    }
    ans = max(ans, len);
    if(ans == 0) cout << "-1" << endl;
    else cout << ans << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    while(tc--)
        process();
    return 0;
}
2nd way
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define endl '\n'
#define f first
#define s second
typedef long long ll;
#define vi std::vector<int>
#define vpi std::vector<std::pair<int,int> >
const int MAXN = 100000 + 10;
using namespace std;
int n, x;
int a[MAXN];
void process(){
	cin >> n >> x;
	ll sum = 0;
	rep(i, 0, n) {
		cin >> a[i];
		sum += a[i];
		sum  %= x;
	}
	if(sum) cout << n << endl;
	else{
		int i = 0, j = n-1;
		while(i < n && (a[i] % x) == 0) i++;
		while(j > -1 && (a[j] % x) == 0) j--;
		if(i== n) cout << "-1" << endl;
		else cout << max(n-1-i, j) << endl;
	}

}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
	int tc; cin >> tc;
	while(tc--)
    process();
    return 0;
}

Problem B : Most socially-distanced subsequence

Point

Design(x)

Big O(time)

Code(x)

#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define pb(x) push_back(x)
#define f first
#define s second
#define endl '\n'
typedef  long long ll;
const int MAXN = 100000 + 10;
using namespace std;

int n;
int a[MAXN];
vi ans;
void process(){
    cin >> n;
    rep(i, 0, n) cin >> a[i];
    ans.clear();
    ans.pb(a[0]);
    rep(i, 1, n-1){
        if(ans.back() < a[i] && a[i] < a[i+1]) continue;
        if(ans.back() > a[i] && a[i] > a[i+1]) continue;
        ans.pb(a[i]);
    }
    ans.pb(a[n-1]);
    cout << ans.size() << endl;
    rep(i, 0, ans.size()) cout << ans[i] << " ";
    cout << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc; cin >> tc;
    while(tc--)
        process();
    return 0;
}

Problem C : Ehab and Prefix MEXs

Point

Design(x)

Big O(time)

Big O(memory)

Code(x)

#include<bits/stdc++.h>
#define all(v) (v).begin(),(v).end()
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
#define vi vector<int>
#define vpi vector<pair<int,int> >
#define pb(x) push_back(x)
#define f first
#define s second
#define endl '\n'
typedef  long long ll;
const int MAXN = 100000 + 10;
using namespace std;

int n;
int a[MAXN];
int b[MAXN];
stack<int> s;
void process(){
	while(!s.empty())s.pop();
	cin >> n;
	rep(i, 0, n){
		cin >> a[i];
		b[i] = -1;
	}
	int mex = 0;
	rep(i, 0, n){
		s.push(i);
		while(a[i] > mex){
			int top = s.top();
			s.pop();
			b[top] = mex++;
		}
	}
	rep(i, 0, n){
		if(b[i] == -1) cout << MAXN << " ";
		else cout << b[i] << " ";
	}cout << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    //int tc; cin >> tc;
    //while(tc--)
        process();
    return 0;
}