Competition/codeforces
Codeforces Round #552 (Div. 3) E. Two Teams
shyram
2019. 4. 17. 13:35
E. Two Teams
https://codeforces.com/contest/1154/problem/E
리스트 STL의 iter를 잘 못다뤄서.. 그냥 리스트를 구현했다.
입력받은 순서대로 리스트에 추가하고, 해당 포인터를 배열에 저장해놓는다. 이때 배열의 index는 입력받은 값이다.
입력이 끝나면 포인터 배열의 끝에서부터 탐색하게 된다(n부터 1까지)
해당 노드가 리스트에 존재하면 노드의 on이 True값을 가지게 된다.
탐색하다 노드가 on되어 있으면 해당 포인터에 접근해서 양옆 k개의 노드를 리스트에서 끊어주자.
n부터 1까지 쭉 반복하면 모든 팀이 구성된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 | #include <bits/stdc++.h> using namespace std; typedef long long ll; int sw; int arr[200001]; struct Node { int index; bool on; Node *prev, *next; }nodes[200005]; int nidx = 0; Node *bring_nodes() { return &nodes[nidx++]; } struct list { Node head, tail; void init() { head.next = &tail; tail.prev = &head; } void push(Node * tempnode) { Node* prevNode = tail.prev; tempnode->prev = prevNode; tempnode->next = &tail; prevNode->next = tempnode; tail.prev = tempnode; } void pop(Node *tempnode, int k) { Node* prevNode = tempnode->prev; Node* nextNode = tempnode->next; while (k--) { if (prevNode != &head) { prevNode->on = false; arr[prevNode->index] = sw; prevNode = prevNode->prev; } if (nextNode != &tail) { nextNode->on = false; arr[nextNode->index] = sw; nextNode = nextNode->next; } } arr[tempnode->index] = sw; tempnode->on = false; prevNode->next = nextNode; nextNode->prev = prevNode; } }L; int a, b, c; int n, m, k; Node *pnode[200005]; int main() { ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); L.init(); cin >> n >> k; for (int i = 0; i < n; i++) { cin >> arr[i]; Node *tempnode = bring_nodes(); tempnode->index = i; tempnode->on = true; pnode[arr[i]] = tempnode; L.push(tempnode); } sw = 1; for (int i = n; i > 0; i--) { if (pnode[i]->on) { L.pop(pnode[i], k); if (sw == 1) sw = 2; else sw = 1; } } for (int i = 0; i < n; i++) cout << arr[i]; return 0; } |