QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#83956#2143. Railroad sortingrania__#WA 0ms3296kbC++143.3kb2023-03-04 17:34:472023-03-04 17:34:51

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-04 17:34:51]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3296kb
  • [2023-03-04 17:34:47]
  • 提交

answer

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 2e5 + 5, P1 = 31, P2 = 37, M = 1e9 + 7;
int pw1[N], pw2[N], inv1[N], inv2[N];
int mul(int a, int b) {
    a = ((a % M) + M) % M;
    b = ((b % M) + M) % M;
    return (a * 1LL * b) % M;
}
#define F first
#define S second
int add(int a, int b) {
    a = ((a % M) + M) % M;
    b = ((b % M) + M) % M;
    return (a + b) % M;
}
int fastPower(int base, int power) {
    if (!power) return 1;
    int ret = fastPower(base, power >> 1);
    ret = mul(ret, ret);
    if (power % 2) ret = mul(ret, base);
    return ret;
}
void pre() {
    pw1[0] = inv1[0] = pw2[0] = inv2[0] = 1;
    int mulInv1 = fastPower(P1, M - 2);
    int mulInv2 = fastPower(P2, M - 2);
    for (int i = 1; i < N; i++) {
        pw1[i] = mul(pw1[i - 1], P1);
        pw2[i] = mul(pw2[i - 1], P2);
        inv1[i] = mul(inv1[i - 1], mulInv1);
        inv2[i] = mul(inv2[i - 1], mulInv2);
    }
}
struct Hash {
    vector<pair<int, int>> prefixHash;
    Hash(string s) {
        prefixHash = vector<pair<int, int>> (s.size(), {0, 0});
        for (int i = 0; i < s.size(); i++) {
            prefixHash[i].F = mul(s[i] - 'a' + 1, pw1[i]);
            prefixHash[i].S = mul(s[i] - 'a' + 1, pw2[i]);
            if (i) prefixHash[i] = {
                        add(prefixHash[i].F, prefixHash[i - 1].F),
                        add(prefixHash[i].S, prefixHash[i - 1].S)
                };
        }
    }
    pair<int, int> getHashVal() {
        return prefixHash.back();
    }
    pair<int, int> getRangeHashVal(int l, int r) {
        return {
                mul(add(prefixHash[r].F, -(l ? prefixHash[l - 1].F : 0)), inv1[l]),
                mul(add(prefixHash[r].S, -(l ? prefixHash[l - 1].S : 0)), inv2[l])
        };
    }
    pair<int,int> conc(int l1,int r1,int l2,int r2)
    {
        auto  f = getRangeHashVal(l1,r1);
        auto s = getRangeHashVal(l2,r2);
        s.first = mul(s.first,pw1[r1-l1+1]);
        s.second = mul(s.second,pw2[r1-l1+1]);
        return {add(f.first,s.first),add(f.second,s.second)};
    }
};
struct dsu{
    int parent[N];
    void makeSet(int node)
    {
        parent[node] = node;
    }
    int findSet(int node)
    {
        if(node == parent[node])
            return node;
        return parent[node] = findSet(parent[node]);
    }
    void unionSet(int a, int b)
    {
        a = findSet(a);
        b = findSet(b);
        if(a != b)
            parent[b] = parent[a];
    }
};
void doWork() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cout << 2 << "\n";
    }
    for (int i = 0; i < n; ++i) {
        cout << -2 << endl;
    }
}


int main() {
    ios::sync_with_stdio(false);
    cout.tie(nullptr);
    cin.tie(nullptr);
//    freopen("bisector.in","r",stdin);
//    freopen("bisector.out","w",stdout);
    int t = 1;
    // cout << primes.size() << endl;
   // cin >> t;
    //pre();
    while (t--) {
        doWork();
    }
    return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3296kb

input:

5
3 1 5 2 4

output:

2
2
2
2
2
-2
-2
-2
-2
-2

result:

wrong answer not sorted, at pos 1 car 4