QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#83956 | #2143. Railroad sorting | rania__# | WA | 0ms | 3296kb | C++14 | 3.3kb | 2023-03-04 17:34:47 | 2023-03-04 17:34:51 |
Judging History
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