QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#776383#7859. BladestormguodongWA 188ms3800kbC++173.2kb2024-11-23 18:26:282024-11-23 18:26:28

Judging History

你现在查看的是最新测评结果

  • [2024-11-23 18:26:28]
  • 评测
  • 测评结果:WA
  • 用时:188ms
  • 内存:3800kb
  • [2024-11-23 18:26:28]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n,k;
class Block{
    public:
        vector<pair<int,int>> ans;
        vector<int> nxt;
        vector<int> mark;
        int n;
        bool exist = 0;
        Block(int _n){
            n = _n;
            exist = 0;
            ans.resize(_n);
            nxt.resize(_n);
            mark.resize(_n);
        }
        void calc(){
            for(int i = n - 1; i >= 0; --i){
                if(mark[i])
                    nxt[i] = i;
                else if(i == n - 1)
                    nxt[i] = 1e9;
                else
                    nxt[i] = nxt[i + 1];
            }
            for(int p = 0; p < n; ++p){
                int st = p,cnt = 0,flag = 0;
                while(1){
                    if(st == n-1 || nxt[st + 1] == 1e9){
                        ans[p] = make_pair(cnt,st);
                        break;
                    }
                    if(st + k >= n){
                        ans[p] = make_pair(cnt + 1,st + k);
                        break;
                    }
                    if(nxt[st + k] == nxt[st]){
                        st = nxt[st];
                    }
                    else{
                        st = st + k;
                    }
                    ++cnt;
                }
            }
        }
        void add(int x){
            exist = 1;
            if(mark[x])
                return;
            mark[x] = 1;
            calc();
        }
        pair<int,int> getAns(int st){
            return ans[st];
        }
        bool Exist(){
            return exist;
        }
};
signed main()
{
    #ifdef NICEGUODONG
        freopen("data.in","r",stdin);
    #endif
    // ios::sync_with_stdio(false);
    int T;
    cin >> T;
    while(T--){
        cin >> n >> k;
        int len;
        if(k * k > n || n <= 3){
            len = n;
        }
        else{
            len = sqrt(n);
        }
        // len = n3
        vector<Block> block((n + len - 1) / len + 1, Block(len));
        int maxx = 0;
        for(int i = 1; i <= n; ++i){
            int x;
            cin >> x;
            maxx = max(maxx,x);
            block[x / len].add(x % len);
            int cur = 0,ans = 0,id = 0,ext = 0;
            while(cur < maxx){
                int l = id * len;
                if(block[id].exist == 0){
                    ++id;
                    ext = 1;
                    continue;
                }
                if(ext == 1){
                    ext = 0;
                    ans++;
                    cur = block[id].nxt[0] + l;
                }
                if(cur >= l){
                    auto &[fee,nxt] = block[id].ans[cur - l];
                    ans += fee;
                    cur = nxt + l;
                }
                else{
                    cur = max(cur + k,block[id].nxt[0] + l);
                    ++ans;
                    auto &[fee,nxt] = block[id].ans[cur - l];
                    ans += fee;
                    cur = nxt + l;
                }
                ++id;
            }
            cout << ans << " ";
        }
        cout << '\n';
    }

}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3748kb

input:

3
7 2
4 7 3 6 1 2 5
11 3
10 7 4 9 6 8 5 1 3 2 11
9 2
1 2 3 7 8 9 4 5 6

output:

1 2 3 3 4 4 4 
1 2 3 3 3 3 3 4 4 4 4 
1 1 2 3 4 4 4 5 5 

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 151ms
memory: 3588kb

input:

40319
1 1
1
2 1
1 2
2 1
2 1
2 2
1 2
2 2
2 1
3 1
1 2 3
3 1
1 3 2
3 1
2 1 3
3 1
2 3 1
3 1
3 1 2
3 1
3 2 1
3 2
1 2 3
3 2
1 3 2
3 2
2 1 3
3 2
2 3 1
3 2
3 1 2
3 2
3 2 1
3 3
1 2 3
3 3
1 3 2
3 3
2 1 3
3 3
2 3 1
3 3
3 1 2
3 3
3 2 1
4 1
1 2 3 4
4 1
1 2 4 3
4 1
1 3 2 4
4 1
1 3 4 2
4 1
1 4 2 3
4 1
1 4 3 2
4 1
...

output:

1 
1 2 
1 2 
1 1 
1 1 
1 2 3 
1 2 3 
1 2 3 
1 2 3 
1 2 3 
1 2 3 
1 1 2 
1 2 2 
1 1 2 
1 2 2 
1 2 2 
1 2 2 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 1 1 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4 
1 2 3 4...

result:

ok 40319 lines

Test #3:

score: -100
Wrong Answer
time: 188ms
memory: 3800kb

input:

50000
10 2
9 3 1 10 2 4 6 5 7 8
10 5
8 3 4 1 2 7 5 9 10 6
10 7
6 7 5 9 1 4 10 2 8 3
10 10
3 1 10 2 6 8 9 4 5 7
10 7
8 9 7 5 6 2 1 10 3 4
10 1
7 1 10 8 9 3 4 6 2 5
10 1
6 7 4 10 3 5 8 9 1 2
10 9
4 6 9 7 3 8 5 1 10 2
10 4
2 6 9 3 10 5 1 4 7 8
10 1
7 4 10 3 6 9 2 5 1 8
10 6
9 5 2 3 1 8 10 7 6 4
10 4
3 ...

output:

1 2 3 4 4 4 5 5 5 5 
1 2 2 2 2 2 2 2 2 2 
1 1 1 2 2 2 2 2 2 2 
1 1 1 1 1 1 1 1 1 1 
1 2 2 2 2 2 2 2 2 2 
1 2 3 4 5 6 7 8 9 10 
1 2 3 4 5 6 7 8 9 10 
1 1 1 1 1 1 1 1 2 2 
1 2 3 3 3 3 3 3 3 3 
1 2 3 4 5 6 7 8 9 10 
1 2 2 2 2 2 2 2 2 2 
1 1 2 2 3 3 3 3 3 3 
1 1 1 1 1 1 1 1 1 1 
1 1 1 1 1 1 1 1 1 1 
1 1...

result:

wrong answer 41st lines differ - expected: '1 2 3 4 5 6 7 8 9 10', found: '1 2 4 5 6 7 8 9 9 10 '