SMU Spring 2023 Trial Contest Round 10

A. Remove Duplicates

#include <bits/stdc++.h>
//#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e3 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
vector<int> a, b;
void solve()
{
    cin >> n;
    set<int> S;
    vector<int> a,b;
    int vis[N] = {0};
    for(int i = 0;i < n; i++){
        int x;
        cin >> x;
        vis[x] ++;
        a.push_back(x);
    }
    for(int i = 0;i < a.size(); i++){
        if(vis[a[i]] == 1){
            b.push_back(a[i]);
        }
        else
        vis[a[i]]--;
    }
    cout << b.size() << endl;
    for(auto i : b){
        cout << i << ' ' ;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

B. File Name

#include <bits/stdc++.h>
//#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e3 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
vector<int> a, b;
void solve()
{
    cin >> n;
    string s;
    cin >> s;
    int ans = 0;
    for(int i = 0; i < s.size(); i++){
        if(s[i]!='x')
            continue;
        m = i;
        while(s[i] == 'x' && i < s.size()){
            i++;
        }
        if(i - m > 2)
            ans += (i - m - 2);
    }
    cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

C. Letters

#include <bits/stdc++.h>
//#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 2e3 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
vector<int> a, b;
void solve()
{
    cin >> n >> m;
    vector<int> a,b;
    cin >> k;
    a.push_back(k);
    for(int i = 1;i < n; i++){
        int x;
        cin >> x;
        a.push_back(x + a[i - 1]);
    }
    for(int i = 0 ;i < m; i++){
        int x;
        cin >> x;
            auto it = lower_bound(a.begin(),a.end(),x) - a.begin();
           if(lower_bound(a.begin(),a.end(),x) == a.begin())
               cout << 1 << ' ' << x << endl;
           else
               cout << it + 1 << ' ' << x - a[it - 1] << endl;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

D.Almost Arithmetic Progression

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t;
/*
*/
void solve()
{
    cin >> n;
    vector<int> a(n);
    for(int i = 0;i < n; i++){
        cin >> a[i];
    }
    if(n <= 2){
        cout << 0 << endl;
        return ;
    }
    int ans = inf;
    for(int i = -1;i <= 1;i ++){
        for(int j = -1; j<= 1; j++){
            vector<int> b(a);
            b[0] += i;
            b[1] += j;
            int d = b[1] - b[0];
            int res = abs(i) + abs(j);
            for(int k = 2; k < n && res <= ans; k++){
                int dd = b[k] - b[k - 1];
                if (dd == d)
                    continue;
                else if(dd == d + 1){
                    b[k]--;
                    res ++;
                }
                else if(dd == d - 1){
                    b[k] ++;
                    res ++;
                }
                else
                    res = inf;
            }
            ans = min(res, ans);
        }
    }
    if(ans == inf)
        cout << -1 << endl;
    else
        cout << ans << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

E.Bus Video System

 #include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t;
/*
*/
int a[N];
void solve()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        a[i] = a[i] + a[i - 1];
    }
    int r = min(m, m - *max_element(a + 1, a + n + 1));
    int l = max(0ll, -*min_element(a + 1, a + n + 1));
    cout << max(0ll, r - l + 1) << endl;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

F.Mentors

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
int a[N];
void solve()
{
    cin >> n >> k;
    vector<int> a(n);
    for(int i = 0;i < n; i++){
        cin >> a[i];
    }
    auto b = a;
    vector<int> c(n,0);
    sort(b.begin(), b.end());
    for(int i = 0;i < a.size(); i++){
        c[i] = lower_bound(b.begin(), b.end(),a[i]) - b.begin();
    }
//    for(auto i : c)
//        cout << i << ' ';
//    cout << endl;
    while(k--){
        int x,y;
        cin >> x >> y;
        x--,y--;
        if(a[x] > a[y])
            c[x]--;
        else if(a[x] < a[y])
            c[y]--;
    }
    for(auto i : c)
        cout << i << ' ';
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}

G.Petya's Exams

#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define endl '\n'
#define int long long

using namespace std;

const int N = 1e5 + 10, mod = 1e9 +7;

//typedef long long ll;
typedef pair<int,int> PII;
//queue<PII> q1;
map<vector<int>, int > mp;
//priority_queue <int,vector<int>,greater<int> > q2;
int n,m,t,k;
/*
*/
int a[N];
struct Time{
    int s,e,d,id;
    bool operator < (const Time &s)const {
        if(e != s.e) return e < s.e;
    }
}day[N];
void solve()
{
    cin >> n >> m;
    vector<int> a(n + 1);
    for(int i = 0;i < m; i++){
        cin >> day[i].s >> day[i].e >> day[i].d ;
        day[i].id = i + 1;
        if(a[day[i].e]) {
            puts("-1");
            exit(0);
        }
        a[day[i].e] = m + 1;
    }
    sort(day, day + n);
    for(auto [s,e,d,id] : day){
        for(int i = s;i < e && d > 0; i++){
            if(a[i])
                continue;
            a[i] = id;
            d--;
        }
        if(d == 0)
            continue;
        puts("-1");
        exit(0);
    }
    for(int i = 1;i <= n; i++){
        cout << a[i] << ' ';
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int Ke_scholar = 1;
    //cin >>  Ke_scholar ;
    while(Ke_scholar--)
        solve();
    return 0;
}