11338 XOR Sum

오랜만에 토요라운드 문제를 풀었다. 

그냥 토요일마다 골드 한두문제씩 푸는 걸 목표로 해야겠다. 

끝나고 지나랑 알고리즘 책 스터디도 하기로 해서 당분간 꾸준히 참석할 듯?

 

오늘 문제는 그렇게 어렵지 않았다.

보니 입력만 있지 삭제는 없어서 그냥 입력 k개만 신경쓰고 k개 이후일 경우에만 작은 수를 제외시키면 된다. 

xor은 두 번 연산시 초기화 되기 때문에 그냥 넣을 때 xor하고 뺄 때 xor하면 돼서 간단했다. 

그럼에도 많이 틀렸는데.... 문자열 입력 받을 시 ios_base::sync_with_stdio(false); cin.tie(NULL); 를 안 해줘서 시간초과가 났다. 

주의하도록 하자. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

void solve() {
    int q, k;
    cin >> q >> k;
    
    priority_queue <int, vector<int>, greater<int> > pq;
    int sum = 0;
    
    for (int i = 0; i < q; i++) {
        string s;
        cin >> s;
            
        if (s == "print") {
            cout << sum << "\n";
            continue;    
        }
        
        int n;
        cin >> n;
        
        pq.push(n);
        sum ^= n;
        
        if (pq.size() > k) {
            sum ^= pq.top();
            pq.pop();
            continue;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t;
    
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    
    return 0;
}