なぜこのコードはTLEになる?
下のコードは、競技プログラミングの問題 バトンリレーゲーム に対する回答です。サンプルはリストを使用したものを載せました。
同じテストケースでサンプルコードはメモリ時間0.03sだったのに対し自分のコードは1.99sを超えTLE (Time Limit Exceeded) となりました。
しかし、この二つのコードの根本的違いが判りません。どなたかご教授願えないでしょうか?
自分で書いたコード
#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;
}
}
}
サンプル
#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;
}
}