AOJ プログラミング応用 トピック#1, トピック#2

#トピック#1
##[ITP2_1_A](https://onlinejudge.u-aizu.ac.jp/problems/ALDS1_4_A)
###Vector

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    vector<int> A;
    int q;
    cin >> q;
    
    rep(i, q){
        int cmd, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> x;
            A.push_back(x);
        }else if(cmd == 1){
            cin >> x;
            cout << A[x] << endl;
        }else if(cmd == 2){
            A.pop_back();
        }
    }

    return 0;
}
```

##[ITP2_1_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/1/ITP2_1_B)
###Deque

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    deque<int> A;
    int q;
    cin >> q;
    
    rep(i, q){
        int cmd, d, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> d >> x;
            if(d==0) A.push_front(x);
            else if(d==1) A.push_back(x);
        }else if(cmd == 1){
            cin >> x;
            cout << A[x] << endl;
        }else if(cmd == 2){
            cin >> d;
            if(d==0) A.pop_front();
            else if(d==1) A.pop_back();
        }
    }
    
    return 0;
}
```

##[ITP2_1_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/1/ITP2_1_C)
###List

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    list<ll> A;
    int q;
    cin >> q;
    
    list<ll>::iterator itr = A.end();
    rep(i, q){
        int cmd, d, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> x;
            A.insert(itr, x);
            itr--;
        }else if(cmd == 1){
            cin >> d;
            if(d>0) for(int i=0; i<d; i++) itr++;
            if(d<0) for(int i=0; i>d; i--) itr--;
        }else if(cmd == 2){
            itr = A.erase(itr);
        }
    }
    
    for(list<ll>::iterator itr = A.begin(); itr != A.end(); itr++){
        cout << *itr << endl;
    }

    return 0;
}
```

##[ITP2_1_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/1/ITP2_1_D)
###Vector II

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, q;
    cin >> n >> q;
    
    vector<vector<int>> A(n);
    
    rep(i, q){
        int cmd, t, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> t >> x;
            A[t].push_back(x);
        }else if(cmd == 1){
            cin >> t;
            if(A[t].size()==0){
                cout << endl;
                continue;
            }else{
                rep(i, A[t].size()){
                    if(i<A[t].size()-1) cout << A[t][i] << ' ';
                    else cout << A[t][i] << endl;
                }
            }
        }else if(cmd == 2){
            cin >> t;
            A[t].clear();
        }
    }

    return 0;
}
```

#トピック#2
##[ITP2_2_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/2/ITP2_2_A)
###Stack

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, q;
    cin >> n >> q;
    
    vector<stack<int>> vec_stack(n);
    
    rep(i, q){
        int cmd, t, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> t >> x;
            vec_stack[t].push(x);
        }else if(cmd == 1){
            cin >> t;
            if(vec_stack[t].size()>0) cout << vec_stack[t].top() << endl;
        }else if(cmd == 2){
            cin >> t;
            if(vec_stack[t].size()>0) vec_stack[t].pop();
        }
    }

    return 0;
}
```

##[ITP2_2_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/2/ITP2_2_B)
###Queue

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, q;
    cin >> n >> q;
    
    vector<queue<int>> vec_queue(n);
    
    rep(i, q){
        int cmd, t, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> t >> x;
            vec_queue[t].push(x);
        }else if(cmd == 1){
            cin >> t;
            if(vec_queue[t].size()>0) cout << vec_queue[t].front() << endl;
        }else if(cmd == 2){
            cin >> t;
            if(vec_queue[t].size()>0) vec_queue[t].pop();
        }
    }

    return 0;
}
```

##[ITP2_2_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/2/ITP2_2_C)
###Priority Queue

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, q;
    cin >> n >> q;
    
    vector<priority_queue<int>> vec_priority_queue(n);
    
    rep(i, q){
        int cmd, t, x;
        cin >> cmd;
        
        if(cmd == 0){
            cin >> t >> x;
            vec_priority_queue[t].push(x);
        }else if(cmd == 1){
            cin >> t;
            if(vec_priority_queue[t].size()>0) cout << vec_priority_queue[t].top() << endl;
        }else if(cmd == 2){
            cin >> t;
            if(vec_priority_queue[t].size()>0) vec_priority_queue[t].pop();
        }
    }

    return 0;
}
```

##[ITP2_2_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/2/ITP2_2_D)
###Splice

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    
    int n, q;
    cin >> n >> q;
    
    vector<list<int>> vec_lsit(n);
    vector<vector<int>> vec_cmd(q);
    
    rep(i, q){
        int cmd, t, x;
        cin >> cmd;
        vec_cmd[i].push_back(cmd);
        
        if(cmd == 0){
            cin >> t >> x;
            vec_cmd[i].push_back(t);
            vec_cmd[i].push_back(x);
        }else if(cmd == 1){
            cin >> t;
            vec_cmd[i].push_back(t);
        }else if(cmd == 2){
            cin >> t >> x;
            vec_cmd[i].push_back(t);
            vec_cmd[i].push_back(x);
        }
    }
    
    rep(i, q){
        int cmd, t, x;
        cmd = vec_cmd[i][0];
        
        if(cmd == 0){
            t = vec_cmd[i][1];
            x = vec_cmd[i][2];
            vec_lsit[t].push_back(x);
        }else if(cmd == 1){
            t = vec_cmd[i][1];
            if(vec_lsit[t].size() == 0){
                cout << endl;
                continue;
            }
            for(list<int>::iterator itr = vec_lsit[t].begin(); itr != vec_lsit[t].end(); itr++){
                list<int>::iterator tmp = itr;
                tmp++;
                if(tmp != vec_lsit[t].end()) cout << *itr << ' ';
                else cout << *itr << endl;
            }
        }else if(cmd == 2){
            t = vec_cmd[i][1];
            x = vec_cmd[i][2];
            vec_lsit[x].splice(vec_lsit[x].end(), vec_lsit[t]);
        }
    }

    return 0;
}
```