The code below is the answer to the competition programming problem baton relay game.I put the sample using the list.
In the same test case, the sample code was 0.03s memory time, while my code was over 1.99s and I got TLE (Time Limit Exceeded).
However, I cannot see the fundamental difference between the two codes.Could someone please teach me?
My own 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 (inti=0;i<n;i++)
using namespace std;
typeedef long long ll;
typeef 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);
}
intst = 0;
rep(i,M){
if(a[i]%2){
intx = st-a[i];
//cout<<x<<"sub"<<endl;
x% = (N-i);
x + = N-i;
x% = (N-i);
list<int>::iteratoritr=stu.begin();
rep(i,x){
itr++;
}
inty=*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;
autoitr=stu.begin();
rep(i,x){
itr++;
}
inty=*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;
}
}
}
Sample
#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 (inti=0;i<n;i++)
using namespace std;
typeedef long long ll;
typeef pair <double long,ll>P;
#define MAX1000000
int N, M, Q;
int A [MAX];
int V [MAX];
int main() {
cin>>N>>M>Q;
for (inti=0;i<M;i++) sin>>A[i];
for(inti=0;i<N;i++)V[i]=1;
list<int>l;
for(inti=0;i<N;i++)l.push_back(i);
list<int>::iteratorit=l.begin();
for(inti=0;i<M;i++){
int a = A[i];
if(a%2==0){
for(intc=0;c<a;c++){
it++;
if(it==l.end())it=l.begin();
}
}
else{
for(intc=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(inti=0;i<Q;i++){
intq;cin>>q;
cout<<V[q] <<endl;
}
}
It feels like I'm looking at it.
When you find the person to whom the next baton will be passed,
Questioner's Code: Follows from the beginning stu.begin() every time.
Sample code: Followed by the next missing person.
There is a difference thatThe key to the problem is that each student declares only 100 or less (very small compared to the maximum N).The interrogator's code may increase the iterator's increments to a value close to N, but the sample code will always be 100 or less.I think there is a big difference around here.
We assume that the remainder of the questioner's code divided by N-i is intended to calculate the travel distance clockwise.Since the remainder is N-i-1, the addition of iterators will also be required approximately O(N)=200,000 times per loop.For example, if you set x to a small negative value (before taking the remainder), you can create this situation.
Originally, you only need to move 100 clockwise and counterclockwise for each loop. (I think the sample code is like that, too.)
You can feel the difference in execution time by providing input generated by Python code such as:
(Also observe the value of x after removing the excess.)
#!/usr/bin/python3
import random
n = 200000
m = n-1
q = 1
print(n,m,q)
for_in range(m):
print(5, end="")
print()
print(0)
# Intended output similar to the following
# 200000 199999 1
# (five of 199999)
# 0
#
# I'm using an odd number of five to make st-a[i] negative.
We expect the difference in efficiency in how the variables stu and l in list<int> in and in samples.
In the case of Self-Written Code, the larger the N value, the longer it takes to move the stuiterator from begin() in the loop of M.
(i.e., trying to maintain in absolute position)
# In the question sentence, the image of "always handing over the position of the baton from the first person to the last position (for convenience)."
On the other hand, in the M loop, the iterator of l moves only the value of A[k] from the previous position, so we expect that it will not take long to move.
(i.e., trying to maintain relative position)
What do you think?
# It may be a snake's foot, but in vector where randomiterator can be used, itr+=x can be written on the move and moved in a constant time, so the code written by yourself may be faster.However, the cost of erase() will increase, so you won't know if it will be really fast until you try it.
If my code execution time is worst, do you mean (log N)*M and the other sample execution time is M*maximum_a_i(0<=maximum_a_i<=100)?
If it's my code, it'll get worse.
Specifically, in the case of "my code", the worst N iterator may be moved for each action in the M loop, so you should consider N*M as the calculation amount.(The implementation repeats itr++, so I think the cost of moving to the end is N instead of log(N))
# M I think the worst case is for everyone to declare "1" in the number of attempts.
# Strictly speaking, N*(N-1)*(N-2)*...*(N-M) is a rough statement.
In the case of "sample", I think it is M*maximum_a_i as per the comment.
© 2024 OneMinuteCode. All rights reserved.