なぜこのコードはTLEになる？


下のコードは、競技プログラミングの問題
[バトンリレーゲーム](https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0301?year=2014)
に対する回答です。サンプルはリストを使用したものを載せました。  
同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded)
となりました。  
しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか？

自分で書いたコード

[code]

    #define _USE_MATH_DEFINES
    #include<math.h>
    #include<deque>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<cmath>
    #include<tuple>
    #include<string>
    #include<chrono>
    #include<functional>
    #include<iterator>
    #include<random>
    #include<unordered_set>
    #include<array>
    #include<map>
    #include<iomanip>
    #include<assert.h>
    #include<bitset>
    #include<stack>
    #include<memory>
    #include<list>
    
    #define INF (1e9)
    #define rep(i,n) for(int i=0;i<n;i++)
    
    using namespace std;
    typedef long long ll;
    typedef pair<double long, ll>P;
    
    int N, M, Q, a[200000], q[100000]; list<int> stu;
    int V[2000000];
    int main() {
    
        cin >> N >> M >> Q;
        rep(i, M) {
            cin >> a[i];
    
        }
    
        rep(i, N) {
    
            stu.push_back(i);
        }
        int st = 0;
        rep(i, M) {
    
            if (a[i] % 2) {
                int x = st - a[i];
                //cout << x << "sub" << endl;
                x %= (N - i);
                x += N - i;
                x %= (N - i);
    
                list<int>::iterator itr = stu.begin();
                rep(i, x) {
                    itr++;
                }
                int y = *itr;
                stu.erase(itr);
                //cout << x <<" ee"<< endl;
    
                V[y] = 1;
                st = x;
            }
            else {
                int x = st + a[i];
                x %= (N - i);
                //cout << x << endl;
                auto itr = stu.begin();
                rep(i, x) {
                    itr++;
                }
                int y = *itr;
                V[y] = 1;
                stu.erase(itr);
                st = x;
            }
        }
    
    
    
        rep(i, Q) {
                cin >> q[i];
    
            if (!V[q[i]]) {
                cout << 1 << endl;
            }
            else {
                cout << 0 << endl;
            }
        }
    
    }
    
[/code]

サンプル

[code]

    #define _USE_MATH_DEFINES
    #include<math.h>
    #include<deque>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #include<iostream>
    #include<set>
    #include<cmath>
    #include<tuple>
    #include<string>
    #include<chrono>
    #include<functional>
    #include<iterator>
    #include<random>
    #include<unordered_set>
    #include<array>
    #include<map>
    #include<iomanip>
    #include<assert.h>
    #include<bitset>
    #include<stack>
    #include<memory>
    #include<list>
    
    #define INF (1e9)
    #define rep(i,n) for(int i=0;i<n;i++)
    
    
    using namespace std;
    typedef long long ll;
    typedef pair<double long, ll>P;
    
    
    #define MAX 1000000
    int N, M, Q;
    int A[MAX];
    int V[MAX];
    
    int main() {
        cin >> N >> M >> Q;
        for (int i = 0; i < M; i++) cin >> A[i];
        for (int i = 0; i < N; i++) V[i] = 1;
        list<int> l;
        for (int i = 0; i < N; i++) l.push_back(i);
        list<int>::iterator it = l.begin();
        for (int i = 0; i < M; i++) {
            int a = A[i];
            if (a % 2 == 0) {
                for (int c = 0; c < a; c++) {
                    it++;
                    if (it == l.end()) it = l.begin();
                }
            }
            else {
                for (int c = 0; c < a; c++) {
                    if (it == l.begin()) {
                        it = l.end();
                        it--;
                    }
                    else {
                        it--;
                    }
                }
            }
            V[*it] = 0;
            it = l.erase(it);
            if (it == l.end()) it = l.begin();
        }
        for (int i = 0; i < Q; i++) {
            int q; cin >> q;
            cout << V[q] << endl;
        }
    }
    
[/code]




「自分で書いたコード」の変数「`stu`」と「サンプル」の変数「`l`」(どちらも`list<int>`)の現在位置の維持の仕方の効率の違いと予想します。

「自分で書いたコード」の場合、`M`のループ内で`stu`の`iterator`を常に`begin()`から該当位置に移動させようとしているため、`N`の値が大きくなればなるほど、移動させるのにかかる時間がかかると予想します。  
(つまり、絶対位置で維持しようとしている)

＃問題文で言えば、「バトンの位置を常に(便宜上の)先頭の人から最終位置まで渡す」イメージ。

一方「サンプル」の場合、`M`のループ内で`l`の`iterator`は前の位置から`A[k]`の値分しか移動させないので、移動させるのに時間がかかってないと予想します。  
(つまり、相対位置で維持しようとしている)

いかがでしょうか?

＃蛇足かも知れませんが、random iteratorが使える`vector`などでは、移動に「`itr +=
x`」と書いて定数時間で位置を移動できるので、「自分で書いたコード」が高速になるかも知れません。ただし、`erase()`のコストが上がるので、本当に高速になるかは試してみないとわからないです。

# コメントに対する追記

> 私のコードの実行時間は最悪の場合,`(log N)*M`で他方サンプルの実行時間は`M*maximum_a_i`
> `(0<=maximum_a_i<=100)`ということでしょうか？

「私のコード」の場合、もっと悪くなると思います。

具体的には、「私のコード」の場合、`M`のループ内の処理ごとに、最悪`N`回iteratorを移動させる可能性があるので、計算量としては「`N *
M`」と考えたほうがよいと思います。(実装では、`itr++`を繰り返しているので、末尾まで移動するコストは`log(N)`ではなく`N`と思います)

＃`M`回の試行で、全員が「1」を宣言するのが最悪ケースと思います。  
＃厳密には、「`N * (N - 1) * (N - 2) * ... * (N - M)`」ですが、大まかに言っています。

「サンプル」の場合、コメント通り`M * maximum_a_i`と思います。

