18917 수열과 쿼리 38 _python, c++

https://www.acmicpc.net/problem/18917

18917번: 수열과 쿼리 38

 

 

 

 

 

 

 

 

 

문제 접근

배열을 만들어서 접근하면 시간초과로 틀릴것이다.

해보진 않았지만 제출현황에 시간초과가 엄청 많았다.

생각해보면 sum이랑 xor연산 모두 배열에 들어있는 숫자들의 순서에 상관없이 추가와 삭제연산을 그때그때마다 해줘도 문제가 없다.

그렇기때문에 50만크기의 배열을 생성할 필요없이 처음 값으로 1과 2를 입력받으면 x값을 sum과 xor연산을 해줘서 저장해두면 끝이다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

python

import sys

input = sys.stdin.readline
"""
1~4 명령어중 출력은 총 합과 xor연산밖에 없음.
두 연산은 모두 배열A에 들어있는 값과 순서를 신경쓸필요 없음.
"""

M = int(input())
sum = 0
xor = 0

for i in range(M):
  q = list(map(int, input().split()))
  if q[0] == 1:
    sum += q[1]
    xor ^= q[1]
  elif q[0] == 2:
    sum -= q[1]
    xor ^= q[1]
  elif q[0] == 3:
    print(sum)
  else:
    print(xor)

 

 

 

 

C++

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  int M;
  cin >> M;
  
  long sum = 0;
  long xr = 0;
  int q;

  for (int i = 0; i < M; i++) {
    cin >> q;
    switch (q) {
    case 1:
      cin >> q;
      sum += q;
      xr ^= q;
      break;
    case 2:
      cin >> q;
      sum -= q;
      xr ^= q;
      break;
    case 3:
      cout << sum << "\n";
      break;
    default:
      cout << xr << "\n";
      break;
    }
  }
}