Codeforces Round #713 (Div.3)

Macros

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define el '\n'
using namespace std;
using ll = long long;

void solution(); int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t; while (t--) solution();
}

A. Spy Detected!

• 구현 포인트 - 범위가 작으니 카운트 배열에 때려넣으면 구현이 편해진다!

그냥 뻔한 문젠데 짜증나게 구네요.

int n; cin >> n;
vector<pair<int,int>> cnt(101);

REP(i,1,n) {
    int x; cin >> x;
    ++cnt[x].first;
    cnt[x].second = i;
}

REP(i,1,100) {
    if (cnt[i].first == 1) {
        cout << cnt[i].second << el;
        return;
    }
}

B. Almost Rectangle

• 점 2개로 직사각형 결정
• 행 또는 열이 겹치지 않는다면 간단하게 교차점 출력
• 겹친다면 케이스 분류. 간단히 맨 끝에 붙어있는 경우만 예외로 바꿔주자.

int n; cin >> n;
string x[n];
bool chk = false;
pair<int,int> a, b;

REP(i,0,n-1) cin >> x[i];
REP(i,0,n-1) REP(j,0,n-1) {
    if (!chk and x[i][j] == '*') {
        a = {i,j};
        chk = true;
    } else if (chk and x[i][j] == '*') b = {i,j};
}

if (a.first == b.first) {
    if (a.first == 0) x[1][a.second] = x[1][b.second] = '*';
    else x[0][a.second] = x[0][b.second] = '*';
} else if (a.second == b.second) {
    if (a.second == 0) x[a.first][1] = x[b.first][1] = '*';
    else x[a.first][0] = x[b.first][0] = '*';
} else x[a.first][b.second] = x[b.first][a.second] = '*';

REP(i,0,n-1) cout << x[i] << el;

C. A-B Palindrome

• 한쪽만 찬 애들이랑 가운데 혼자 있는 애들부터 채우고 시작하자.
• 남은거는 개수 보면서 적당히 채워주자.
• 진짜 누가 만들었냐... 개싫다...

int a, b; string s;
cin >> a >> b >> s;
int cnt = 0;

for (int i = 0, j = size(s)-1; i < size(s); ++i, --j) {
    if (s[i] != s[j]) {
        if (s[i] == '?') s[i] = s[j];
        else if (s[j] == '?') s[j] = s[i];
        else {cout << -1 << el; return;}
    }
    if (s[i] == '?') {
        if (i == j) {
            if (a%2 == 1) s[i] = '0';
            else if (b%2 == 1) s[i] = '1';
        } else ++cnt;
    }
}

for (char c : s) {
    if (c == '0') --a;
    else if (c == '1') --b;
}

for (int i = 0, j = size(s)-1; i < size(s); ++i, --j) {
    if (s[i] != '?') continue;
    if (a) {
        s[i] = s[j] = '0';
        a -= 2;
    } else {
        s[i] = s[j] = '1';
        b -= 2;
    }
}

if (a or b) {cout << -1 << el; return;}
cout << s << el;

D. Corrupted Array

• 원소들이 전부 자연수라는 조건이 주어진다.
• 당연히 원소들의 합이 그냥 원소들보다 클 것이다.
• 따라서 정렬을 한다.
• 가장 큰 원소는 빼거나 합으로 쓰인다.
• 뺄 경우, 그 다음으로 큰 원소가 합으로 쓰인다.
• 구현 쉬워서 너무 젛당 ㅎㅎ
• 주석으로 식 정리 적어놓았다.

int n, a[N];
ll sum = 0;
cin >> n; n += 2;
REP(i,1,n) cin >> a[i], sum += a[i];
sort(a+1,a+n+1);

//1) a[1]+...a[k-1]+a[k+1]+...+a[n-1] == a[n]
// a[1]+...+a[n-1]-a[k] == a[n]
// a[k] == (a[1]+...+a[n-1])-a[n]

REP(i,1,n-1) {
    if (a[i] == (sum-a[n])-a[n]) {
        REP(j,1,n-1) if (j != i)
            cout << a[j] << ' ';
        cout << el;
        return;
    }
}

//2) a[1]+...+a[n-2] == a[n-1]

if (sum-a[n-1]-a[n] == a[n-1]) {
    REP(i,1,n-2) cout << a[i] << ' ';
    cout << el;
    return;
}
cout << -1 << el;
return;

1512E - Permutation by Sum

 

1512F - Education

 

G. Short Task

• 전처리 때문에 매크로 없는 풀 코드로 올림.
• multiplicative function은 다 sieve 응용임.
• 여기서 least prime factor 같은거 따지면서 어렵게 들어가거나, 쉽게 sieve 약간의 변형으로 들어가거나 차이.
• 역시 후자가 낫겠지?

#include <bits/stdc++.h>
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define el '\n'
using namespace std;

const int N = 1e7+3;
int divisor[N], ans[N];

int main() {
    ans[1] = divisor[1] = 1;
    REP(x,2,N-1) {
        divisor[x] += x+1;
        for (int u = x+x; u < N; u += x)
            divisor[u] += x;
            if (divisor[x] < N and !ans[divisor[x]])
                ans[divisor[x]] = x;
    }
    int t; cin >> t;
    while (t--) {
        int c; cin >> c;
        if (ans[c]) cout << ans[c] << el;
        else cout << -1 << el;
    }
}