QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#696870 | #7698. ISBN Conversion | snowythecat | AC ✓ | 4ms | 18836kb | C++20 | 12.1kb | 2024-11-01 04:26:57 | 2024-11-01 04:26:58 |
Judging History
answer
//must be compiled with c++20
/*
#pragma GCC target ("avx2")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
*/
#include <algorithm>
#include <bits/stdc++.h>
#include <cerrno>
#include <ext/pb_ds/assoc_container.hpp>
#include <type_traits>
using namespace __gnu_pbds;
using namespace std;
#define fasterthanlight cin.tie(0); ios::sync_with_stdio(0);
#define ll long long
#define lll __int128
const ll inf = 1e9 + 7;
const ll inf2 = 1e9 + 9;
const ll inff= 998244353;
const ll infh = (1LL << 61) - 1;
#define pll pair<ll,ll>
#define pii pair<int,int>
#define vi vector<int>
#define vll vector<ll>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define pb push_back
#define f0(i,n) for (int i=0;i<n;i++)
#define f1(i,n) for (int i=1;i<=n;i++)
#define ff0(i,n) for (int i=n-1;i>-1;i--)
#define ff1(i,n) for (int i=n;i>0;i--)
#define fs(i,a,b) for (int i=a;i<b;i++)
#define testcases int tzxhicjkha; cin>>tzxhicjkha;while (tzxhicjkha--)
#define usingfloats cout<<setprecision(20)
#define ineedtohash mll iqknabxiopk=1;for (ll iqknabxiop=0;iqknabxiop<HASHPOWMAX;iqknabxiop++){pows[iqknabxiop]=iqknabxiopk;iqknabxiopk*=B;}
#define sz(x) ((int)(x.size()))
template <class T> auto vect(const T& v, int n) { return vector<T>(n, v); }
template <class T, class... D> auto vect(const T& v, int n, D... m) {
return vector<decltype(vect(v, m...))>(n, vect(v, m...));
}
//2*10^6 powers for hashing
const ll HASHPOWMAX=2000005;
int msb(int n)
{
if (n==0){
//cout<<"F";
return 0;
}
int k = __builtin_clz(n);
return 31 - k;
}
ll lmsb(ll n)
{
if (n==0){
//cout<<"F";
return 0;
}
int k = __builtin_clzll(n);
return 63 - k;
}
//I have no idea if the below code is safe or good
istream &operator>>(istream &is,__int128 &v) {
string s;
is>>s;
v=0;
for(auto &it:s) if(isdigit(it)) v=v*10+it-'0';
if(s[0]=='-') v*=-1;
return is;
}
ostream &operator<<(ostream &os,const __int128 &v) {
if(v==0) return (os<<"0");
__int128 num=v;
if(v<0) os<<'-',num=-num;
string s;
for(;num>0;num/=10) s.pb((char)(num%10)+'0');
reverse(all(s));
return (os<<s);
}
/*
template<typename T, typename Q>ostream &operator<<(ostream &os,const pair<T,Q> &v) {
return (os<<v.first<<" "<<v.second);
}
*/
//some cursed cin vector shit
template<typename T> istream &operator>>(istream &is,vector<T> &v) {
for (T&i:v){
is>>i;
}
return is;
}
template<typename T> ostream &operator<<(ostream &os,const vector<T> &v) {
if (v.empty()){
return os;
}
for (int i=0;i<v.size()-1;i++){
os<<v[i]<<" ";
}
return os<<v[v.size()-1];
}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
//const ll B = 100;
const ll B = uniform_int_distribution<ll>(1000, inf - 1)(rng);
/*
//some cursed code
//allows int x=in;
struct {
template<class T>
operator T() {
T x; std::cin >> x; return x;
}
} in;
//breaks if string
//so do string s = (string)in;
*/
//ty Mark for modint code that I will change
template<long long MOD>
struct ModInt {
long long v;
ModInt() {
v=0;
}
ModInt(long long _v) {
v = _v % MOD;
if (v < 0) {
v += MOD;
}
}
friend ModInt pow(ModInt base, long long exp) {
ModInt res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
ModInt &operator+=(ModInt b) {
if ((v += b.v) >= MOD) {
v -= MOD;
}
return *this;
}
ModInt &operator-=(ModInt b) {
if ((v -= b.v) < 0) {
v += MOD;
}
return *this;
}
ModInt &operator*=(ModInt b) {
if constexpr (MOD==infh){
//UNSAFE CODE PROBABLY
uint64_t l1 = uint32_t(v), h1 = v >> 32;
uint64_t l2 = uint32_t(b.v), h2 = b.v >> 32;
uint64_t l = l1 * l2, m = l1 * h2 + l2 * h1, h = h1 * h2;
uint64_t ret = (l & MOD) + (l >> 61) + (h << 3) + (m >> 29) + (m << 35 >> 3) + 1;
ret = (ret & MOD) + (ret >> 61);
ret = (ret & MOD) + (ret >> 61);
v = ret - 1;
return *this;
}
else if constexpr (MOD<=INT_MAX){
//if less than or equal to INT_MAX, lll isn't needed
v=v * b.v % MOD;
return *this;
}
else{
v = (__int128)1 * v * b.v % MOD;
return *this;
}
}
//division is scuffed
ModInt &operator/=(ModInt b) {
*this *= pow(b, MOD - 2);
return *this;
}
friend ModInt operator+(ModInt a, ModInt b) {
return a += b;
}
friend ModInt operator-(ModInt a, ModInt b) {
return a -= b;
}
friend ModInt operator*(ModInt a, ModInt b) {
return a *= b;
}
friend ModInt operator/(ModInt a, ModInt b) {
return a /= b;
}
friend istream &operator>>(istream &is, ModInt &a) {
long long x;
is >> x;
a = ModInt(x);
return is;
}
friend ostream &operator<<(ostream &os, ModInt a) {
return os << a.v;
}
bool operator==(const ModInt& y) const{
return v == y.v;
}
bool operator!=(const ModInt& y) const{
return v != y.v;
}
ModInt& operator++() {
v++;
if (v == MOD) v = 0;
return *this;
}
ModInt& operator--() {
if (v == 0) v = MOD;
v--;
return *this;
}
ModInt operator++(int) {
ModInt result = *this;
++*this;
return result;
}
ModInt operator--(int) {
ModInt result = *this;
--*this;
return result;
}
//bad operators for completeness sake
bool operator>(const ModInt& y) const{
return v > y.v;
}
bool operator>=(const ModInt& y) const{
return v >= y.v;
}
bool operator<=(const ModInt& y) const{
return v <= y.v;
}
bool operator<(const ModInt& y) const{
return v < y.v;
}
};
using mll = ModInt<infh>;
using mint = ModInt<inf>;
using minf = ModInt<inff>;
ll exp(ll x, ll n, ll m=inf) {
assert(n >= 0);
x %= m; // note: m * m must be less than 2^63 to avoid ll overflow
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x % m; }
x = x * x % m;
n /= 2;
}
return res;
}
ll expu(ll x, ll n) {
assert(n >= 0);
ll res = 1;
while (n > 0) {
if (n % 2 == 1) { res = res * x; }
x = x * x;
n /= 2;
}
return res;
}
mll exph(mll base, ll exp) {
mll res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
minf expf(minf base, ll exp) {
minf res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
mint expo(mint base, ll exp) {
mint res = 1;
while (exp) {
if (exp & 1) {
res *= base;
}
base *= base;
exp >>= 1;
}
return res;
}
vector<mll> pows(HASHPOWMAX);
const mll HMODINV=exph(B,infh-2);
struct hashPart {
mll value;
int len;
hashPart() {
value=0;
len=0;
}
hashPart(mll x, int y) : value(x), len(y) {}
hashPart operator+=(hashPart b) {
hashPart a=hashPart(value * pows[b.len] + b.value, len + b.len);
(*this).value=a.value;
(*this).len=a.len;
return *this;
}
hashPart operator+(hashPart b) {
return hashPart(value * pows[b.len] + b.value, len + b.len);
}
bool operator==(hashPart b) {
return value == b.value;
}
};
template<class T>
struct hashString {
vector<mll> hash;
hashString(T s) {
hash.resize(int(s.size()) + 1);
for (int i = 0; i < int(s.size()); i++) {
hash[i + 1] = (hash[i] * B + s[i]);
}
while (int(pows.size()) < int(hash.size())) {
pows.push_back(pows.back() * B);
}
}
hashPart getHash(int l, int r) {
return hashPart(hash[r] -hash[l] * pows[r - l], r - l);
}
hashPart getHash() {
return getHash(0, hash.size() - 1);
}
};
//I don't understand the below code, all I know is it's good for hashing apparently
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
// http://xorshift.di.unimi.it/splitmix64.c
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
ll es(ll x1, ll y1, ll x2, ll y2){
return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
ll man(ll x1, ll y1, ll x2, ll y2){
return abs(x1-x2)+abs(y1-y2);
}
minf choose(int n,int k){
if (k>n){
return 0;
}
minf ret=1;
for (int i=n;i>n-k;i--){
ret*=i;
}
for (int i=1;i<=k;i++){
ret/=i;
}
return ret;
}
//stolen from geeks for geeks
vector<int> sieve(int n)
{
// Create a boolean array "prime[0..n]" and initialize
// all entries it as true. A value in prime[i] will
// finally be false if i is Not a prime, else true.
bool prime[n + 1];
memset(prime, true, sizeof(prime));
for (int p = 2; p * p <= n; p++) {
// If prime[p] is not changed, then it is a prime
if (prime[p] == true) {
// Update all multiples of p greater than or
// equal to the square of it numbers which are
// multiple of p and are less than p^2 are
// already been marked.
for (int i = p * p; i <= n; i += p)
prime[i] = false;
}
}
vector<int> ret;
// Print all prime numbers
for (int p = 2; p <= n; p++)
if (prime[p])
ret.pb(p);
return ret;
}
void setup(){
}
typedef tree<double,null_type,less_equal<double>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;
void solve(){
string inp;
cin>>inp;
string inp2;
//check hyphen count
int hyphencount=0;
for (int i=0;i<inp.size();i++){
if (inp[i]=='-'){
hyphencount++;
}
else{
if (inp[i]=='X'){
if (i!=inp.size()-1){
cout<<"invalid\n";
return;
}
inp2+='0'+10;
continue;
}
inp2+=inp[i];
}
}
for (int i=0;i<inp.size()-1;i++){
if (inp[i]=='-'&&inp[i+1]=='-'){
cout<<"invalid\n";
return;
}
}
if (hyphencount>3){
cout<<"invalid\n";
return;
}
if (hyphencount==3){
if (inp[inp.size()-2]!='-'){
cout<<"invalid\n";
return;
}
}
if (inp.size()-hyphencount!=10){
cout<<"invalid\n";
return;
}
if (inp[0]=='-'||inp[inp.size()-1]=='-'){
cout<<"invalid\n";
return;
}
//check checksum
//cout<<inp2<<"\n";
int checksum=0;
for (int i=0;i<10;i++){
checksum+=(10-i)*(inp2[i]-'0');
}
if (checksum%11){
cout<<"invalid\n";
return;
}
inp2="978"+inp2.substr(0,9);
checksum=0;
for (int i=0;i<12;i+=2){
checksum+=inp2[i]-'0';
checksum+=3*(inp2[i+1]-'0');
}
cout<<978<<"-"<<inp.substr(0,inp.size()-1)<<(char)('0'+((10-(checksum%10))%10))<<"\n";
}
signed main() {
setup();
//usingfloats;
fasterthanlight;
//ineedtohash;
testcases{
solve();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 18836kb
input:
4 3-540-4258-02 039428013X 3-540-42580-2 0-14-028333-3
output:
invalid 978-0394280134 978-3-540-42580-9 invalid
result:
ok 4 lines
Test #2:
score: 0
Accepted
time: 0ms
memory: 18692kb
input:
25 ---------- ----------- ------------ ------------- XXXXXXXXXX XXXXXXXXXXX XXXXXXXXXXXX XXXXXXXXXXXXX ---------X ----------X -----------X 01234567890 012345678901 0123456789012 -0123456789- 0123456789- -0123456789 01--23456789 012345678--9 0123456789-- --0123456789 98765432-1 987-654-321 87-645-32-...
output:
invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid
result:
ok 25 lines
Test #3:
score: 0
Accepted
time: 0ms
memory: 18836kb
input:
5 71234567X1 71234567X-1 2-2345678-9 8X-7X-123456 7123X8123X
output:
invalid invalid invalid invalid invalid
result:
ok 5 lines
Test #4:
score: 0
Accepted
time: 0ms
memory: 18680kb
input:
10 3-540-42580-X 3-540-42580-3 0393609394 0-19-853453-9 0070131510 0070131512 0070131514 0070131516 0070131518 007013151X
output:
invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 0ms
memory: 18708kb
input:
11 767-13423100 65955-01-15-1 778592-4222 3283-138-073 8-802896-37-4 514-2481525 356-52708-6-6 4-810-73599-7 3-28438-244-8 1-98-2031209 82-54-55344X
output:
invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid invalid
result:
ok 11 lines
Test #6:
score: 0
Accepted
time: 3ms
memory: 18744kb
input:
12 0123456789 0-19-853453-1 0070131511 0-07-0131511 039428013-X 0-39-428013X 0-3942801-3X 0131103628 3-540-42580-2 3540425802 1535956828 1535-9-5682-8
output:
978-0123456786 978-0-19-853453-2 978-0070131514 978-0-07-0131514 978-039428013-4 978-0-39-4280134 978-0-3942801-34 978-0131103627 978-3-540-42580-9 978-3540425809 978-1535956826 978-1535-9-5682-6
result:
ok 12 lines
Test #7:
score: 0
Accepted
time: 3ms
memory: 18608kb
input:
10 69289-01810 07-8-2406750 4946302-980 91-45-00652-0 2526831830 8370591930 022-18967-4-0 86340-22-25-0 862-57-6642-0 1691783730
output:
978-69289-01810 978-07-8-2406757 978-4946302-985 978-91-45-00652-8 978-2526831832 978-8370591939 978-022-18967-4-3 978-86340-22-25-4 978-862-57-6642-6 978-1691783731
result:
ok 10 lines
Test #8:
score: 0
Accepted
time: 0ms
memory: 18692kb
input:
10 5-401032021 5240-54-427-1 9-180-978371 931-918-0741 4696037371 4087-1938-6-1 87-000442-6-1 6917-1319-11 1-765295351 5031540591
output:
978-5-401032027 978-5240-54-427-9 978-9-180-978378 978-931-918-0740 978-4696037373 978-4087-1938-6-2 978-87-000442-6-5 978-6917-1319-14 978-1-765295351 978-5031540596
result:
ok 10 lines
Test #9:
score: 0
Accepted
time: 0ms
memory: 18628kb
input:
10 3-457991-81-2 39984-91252 423300-4-932 3275898582 9366799-442 0557387302 45-91615812 251-19985-7-2 6055184192 81622230-0-2
output:
978-3-457991-81-7 978-39984-91258 978-423300-4-936 978-3275898589 978-9366799-445 978-0557387304 978-45-91615812 978-251-19985-7-1 978-6055184193 978-81622230-0-0
result:
ok 10 lines
Test #10:
score: 0
Accepted
time: 0ms
memory: 18728kb
input:
10 7876-3592-1-3 79129531-83 9-109-06704-3 82865161-33 2-9-35967283 49919695-73 7576775513 3-843660123 004739-25-33 509-758-044-3
output:
978-7876-3592-1-0 978-79129531-81 978-9-109-06704-6 978-82865161-32 978-2-9-35967283 978-49919695-77 978-7576775518 978-3-843660129 978-004739-25-35 978-509-758-044-4
result:
ok 10 lines
Test #11:
score: 0
Accepted
time: 0ms
memory: 18528kb
input:
10 27-6658-1154 457995-2774 0-878349-634 8230808074 663-1-368014 9439-7026-6-4 365-0-59504-4 0158386574 902-1-41617-4 8573813814
output:
978-27-6658-1153 978-457995-2779 978-0-878349-630 978-8230808078 978-663-1-368016 978-9439-7026-6-2 978-365-0-59504-1 978-0158386577 978-902-1-41617-5 978-8573813814
result:
ok 10 lines
Test #12:
score: 0
Accepted
time: 0ms
memory: 18640kb
input:
10 800-978040-5 4855-4-6463-5 61561839-65 9830-08479-5 2859817395 00324136-45 0985-8-6474-5 6624604875 0-83181632-5 32786193-15
output:
978-800-978040-6 978-4855-4-6463-7 978-61561839-65 978-9830-08479-4 978-2859817398 978-00324136-41 978-0985-8-6474-3 978-6624604879 978-0-83181632-2 978-32786193-10
result:
ok 10 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 18568kb
input:
10 248-746984-6 50-140-8997-6 96-8-622617-6 58-213-48056 03497-12-026 3712-885946 319-8564-506 2-3-62643476 756359-764-6 582-97771-2-6
output:
978-248-746984-6 978-50-140-8997-5 978-96-8-622617-1 978-58-213-48050 978-03497-12-024 978-3712-885943 978-319-8564-509 978-2-3-62643477 978-756359-764-2 978-582-97771-2-8
result:
ok 10 lines
Test #14:
score: 0
Accepted
time: 0ms
memory: 18644kb
input:
10 9703497217 3414631237 559383597-7 4545227287 72344-0-2667 741-7414567 91752-4984-7 0545975867 1-817640097 4073-3-5268-7
output:
978-9703497218 978-3414631237 978-559383597-0 978-4545227283 978-72344-0-2664 978-741-7414569 978-91752-4984-1 978-0545975865 978-1-817640092 978-4073-3-5268-6
result:
ok 10 lines
Test #15:
score: 0
Accepted
time: 0ms
memory: 18540kb
input:
10 30-6751714-8 720022041-8 8122-182-348 45-98765-20-8 387750-0048 51371-962-58 0-547777-418 2248735448 78-89-298978 6-16533168-8
output:
978-30-6751714-8 978-720022041-4 978-8122-182-347 978-45-98765-20-6 978-387750-0040 978-51371-962-53 978-0-547777-412 978-2248735449 978-78-89-298971 978-6-16533168-5
result:
ok 10 lines
Test #16:
score: 0
Accepted
time: 4ms
memory: 18716kb
input:
10 3863994019 1-883158419 40-88994949 56-6-201673-9 6-694343-779 52745031-79 0-243850-99-9 78-31645799 0677183259 2874-587109
output:
978-3863994013 978-1-883158415 978-40-88994949 978-56-6-201673-6 978-6-694343-777 978-52745031-74 978-0-243850-99-0 978-78-31645792 978-0677183251 978-2874-587108
result:
ok 10 lines
Test #17:
score: 0
Accepted
time: 0ms
memory: 18716kb
input:
10 407303295X 9-475-98657-X 827-522618-X 280455564X 1975-7120-3X 758-256152-X 090330614X 271696-6-63X 534942744X 53628-6680X
output:
978-4073032953 978-9-475-98657-6 978-827-522618-9 978-2804555641 978-1975-7120-37 978-758-256152-5 978-0903306140 978-271696-6-634 978-5349427442 978-53628-66808
result:
ok 10 lines