Asynchronous Processor

문제

링크: Asynchronous Processor

풀이

입력으로 주어지는 대입 연산 중 마지막 인덱스를 $L$ 이라 합시다.

마지막 대입 연산의 수행 시각 $T = L$ 로 고정합시다.

그렇다면 $T < i$ 인 덧셈은 모두 더해집니다.

$i < T$ 인 덧셈은 async인 경우만 더해지거나 더해지지 않을 수 있습니다.

집합 $S$ 에 async인 대입 연산의 $v$ 만 넣고 결과 집합을 구해 봅시다. $L$ 이 sync 대입인 경우는 따로 처리해주면 됩니다.

$i < T$ 라면 async인 경우만 $S = S \cup (S + v_i)$ 로 갱신합니다. $T < i$ 인 덧셈의 경우 $S = S + v_i$ 로 갱신합니다.

집합 계산에 bitset을 사용하면 $O(n^2v / 64)$ 에 계산할 수 있습니다.

실행 시각을 $L$ 과 $L + 1$ 사이부터 $n$ 과 $n + 1$ 사이까지 바꿔가면서 나오는 모든 집합의 합집합을 구하면 모든 결과 집합을 구할 수 있습니다.

$t - 1 < T < t$ 일때 집합을 $S$ 라 하면 $t < T < t + 1$ 일때 집합은

$v_t$ 가 sync인 경우 더해질 수 없으므로 $S = S - v_t$ 로 업데이트 합니다. $v_t$ 가 async인 경우 더해질 수도, 아닐 수도 있으므로 $S = S \cup (S - v_t)$ 로 업데이트 합니다.

$T$ 의 위치가 $1$ 만큼 바뀔 때에는 $O(nv / 64)$ 에 계산할 수 있으므로 총 시간 복잡도는 $O(n^2v / 64)$ 입니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
struct Query {
    bool add;
    int v;
    bool async;
};
 
constexpr int SZ = 1 << 20;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    vector<Query> queries(n + 1);
    for (int i = 1; i <= n; i++) {
        char op;
        int v;
        string tok;
 
        cin >> op >> v >> tok;
 
        Query &q = queries[i];
        q.add = (op == '+');
        q.v = v;
        q.async = (tok == "async");
    }
 
    bitset<SZ> res;
    int lastAssign = -1;
    for (int i = 1; i <= n; i++) {
        if (queries[i].add) continue;
 
        if (queries[i].async) res[queries[i].v] = true;
        lastAssign = i;
    }
 
    if (lastAssign == -1) {
        cout << 1;
        return 0;
    }
 
    for (int i = 1; i <= n; i++) {
        if (not queries[i].add) continue;
 
        if (lastAssign < i) res <<= queries[i].v;
        else if (queries[i].async) res |= res << queries[i].v;
    }
 
    bitset<SZ> ans = res;
    for (int i = lastAssign + 1; i <= n; i++) {
        if (not queries[i].async) res >>= queries[i].v;
        else res |= res >> queries[i].v;
 
        ans |= res;
    }
 
    res.reset();
    res[queries[lastAssign].v] = true;
    for (int i = 1; i <= n; i++) {
        if (not queries[i].add) continue;
 
        if (lastAssign < i) res <<= queries[i].v;
        else if (queries[i].async) res |= res << queries[i].v;
    }
 
    ans |= res;
 
    cout << ans.count();
 
    return 0;
}

풀이

입력으로 주어지는 대입 연산 중 마지막 인덱스를

L

이라 합시다.

마지막 대입 연산의 수행 시각

T = L

로 고정합시다.

그렇다면

T < i

인 덧셈은 모두 더해집니다.

i < T

인 덧셈은 async인 경우만 더해지거나 더해지지 않을 수 있습니다.

집합

S

에 async인 대입 연산의

v

만 넣고 결과 집합을 구해 봅시다.

L

이 sync 대입인 경우는 따로 처리해주면 됩니다.

i < T

라면 async인 경우만

S = S \cup (S + v_i)

로 갱신합니다.

T < i

인 덧셈의 경우

S = S + v_i

로 갱신합니다.

집합 계산에 bitset을 사용하면

O(n^2v / 64)

에 계산할 수 있습니다.

실행 시각을

L

과

L + 1

사이부터

n

과

n + 1

사이까지 바꿔가면서 나오는 모든 집합의 합집합을 구하면 모든 결과 집합을 구할 수 있습니다.

t - 1 < T < t

일때 집합을

S

라 하면

t < T < t + 1

일때 집합은

v_t

가 sync인 경우 더해질 수 없으므로

S = S - v_t

로 업데이트 합니다.

v_t

가 async인 경우 더해질 수도, 아닐 수도 있으므로

S = S \cup (S - v_t)

로 업데이트 합니다.

T

의 위치가

1

만큼 바뀔 때에는

O(nv / 64)

에 계산할 수 있으므로 총 시간 복잡도는

O(n^2v / 64)

입니다.

코드

#include <bits/stdc++.h>
using namespace std;
 
struct Query {
    bool add;
    int v;
    bool async;
};
 
constexpr int SZ = 1 << 20;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    int n;
    cin >> n;
 
    vector<Query> queries(n + 1);
    for (int i = 1; i <= n; i++) {
        char op;
        int v;
        string tok;
 
        cin >> op >> v >> tok;
 
        Query &q = queries[i];
        q.add = (op == '+');
        q.v = v;
        q.async = (tok == "async");
    }
 
    bitset<SZ> res;
    int lastAssign = -1;
    for (int i = 1; i <= n; i++) {
        if (queries[i].add) continue;
 
        if (queries[i].async) res[queries[i].v] = true;
        lastAssign = i;
    }
 
    if (lastAssign == -1) {
        cout << 1;
        return 0;
    }
 
    for (int i = 1; i <= n; i++) {
        if (not queries[i].add) continue;
 
        if (lastAssign < i) res <<= queries[i].v;
        else if (queries[i].async) res |= res << queries[i].v;
    }
 
    bitset<SZ> ans = res;
    for (int i = lastAssign + 1; i <= n; i++) {
        if (not queries[i].async) res >>= queries[i].v;
        else res |= res >> queries[i].v;
 
        ans |= res;
    }
 
    res.reset();
    res[queries[lastAssign].v] = true;
    for (int i = 1; i <= n; i++) {
        if (not queries[i].add) continue;
 
        if (lastAssign < i) res <<= queries[i].v;
        else if (queries[i].async) res |= res << queries[i].v;
    }
 
    ans |= res;
 
    cout << ans.count();
 
    return 0;
}

Asynchronous Processor

문제

풀이

코드

댓글

Asynchronous Processor

문제

풀이

코드

댓글