Submission #481265

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
481265	2021-10-20T07:36:42 Z	FatihSolak	Collider (IZhO11_collider)	C++17	100 / 100	525 ms	4192 KB

collider

#include <bits/stdc++.h>
#define N 1000005
#define M 1005
using namespace std;
const int block_size = M;
deque<char> block[M];
void solve(){
    int n,m;
    cin >> n >> m;
    string s;
    cin >> s;
    assert(n < N);
    for(int i=0;i<n;i++){
        block[i/block_size].push_back(s[i]);
    }
    while(m--){
        char type;
        cin >> type;
        if(type == 'a'){
            int a,b;
            cin >> a >> b;
            a--;
            b--;
            vector<char> tmp;            
            char add;
            for(int i = 0;block[a/block_size].size();i++){
                if(i != a%block_size){
                    tmp.push_back(block[a/block_size].front());
                }
                else add = block[a/block_size].front();
                block[a/block_size].pop_front();
            }
            for(auto u:tmp){
                block[a/block_size].push_back(u);
            }
            if(block[a/block_size  + 1].size()){
                block[a/block_size].push_back(block[a/block_size  + 1].front());
            }
            for(int i=a/block_size  + 1;block[i].size();i++){
                block[i].pop_front();
                if(block[i+1].size()){
                    block[i].push_back(block[i+1].front());
                }
            }
            tmp.clear();
            char last = '.';
            for(int i = 0;block[b/block_size].size();i++){
                if(i == b%block_size)tmp.push_back(add);
                if(tmp.size() < block_size){
                    tmp.push_back(block[b/block_size].front());
                }
                else last = block[b/block_size].front();
                block[b/block_size].pop_front();
            }
            if(b == n-1)tmp.push_back(add);
            for(auto u:tmp){
                block[b/block_size].push_back(u);
            }
            for(int i=b/block_size  + 1;last != '.';i++){
                block[i].push_front(last);
                if(block[i].size() > block_size){
                    last = block[i].back();
                    block[i].pop_back();
                }
                else last = '.';
            }
            /*
            for(int j=0;block[j].size();j++){
                for(int i=0;i<block[j].size();i++){
                    cout << block[j][i];
                }   
            }
            cout << endl;*/
        }
        if(type == 'q'){
            int pos;
            cin >> pos;
            pos--;
            cout << block[pos/block_size][pos%block_size] << endl;
        }
    }
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    #ifdef Local
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    int t=1;
    //cin>>t;
    while(t--){
        solve();
    }
    #ifdef Local
    cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	972 KB	Output is correct
2	Correct	286 ms	972 KB	Output is correct
3	Correct	146 ms	1100 KB	Output is correct
4	Correct	171 ms	3512 KB	Output is correct
5	Correct	342 ms	3432 KB	Output is correct
6	Correct	415 ms	3776 KB	Output is correct
7	Correct	419 ms	4148 KB	Output is correct
8	Correct	177 ms	3980 KB	Output is correct
9	Correct	525 ms	4192 KB	Output is correct
10	Correct	340 ms	4072 KB	Output is correct