QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696870#7698. ISBN ConversionsnowythecatAC ✓4ms18836kbC++2012.1kb2024-11-01 04:26:572024-11-01 04:26:58

Judging History

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

  • [2024-11-01 04:26:58]
  • 评测
  • 测评结果:AC
  • 用时:4ms
  • 内存:18836kb
  • [2024-11-01 04:26:57]
  • 提交

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();
    }


}

Details

Tip: Click on the bar to expand more detailed information

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