QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #709800 | #8058. Binary vs Ternary | icealsoheat | WA | 0ms | 3840kb | C++20 | 6.5kb | 2024-11-04 16:54:53 | 2024-11-04 16:54:54 |
Judging History
answer
#pragma GCC optimize(3) //O2优化开启
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int mod=998244353;
const int MX=0x3f3f3f3f3f3f3f3f;
//inline int read() //快读
//{
// int xr=0,F=1; char cr;
// while(cr=getchar(),cr<'0'||cr>'9') if(cr=='-') F=-1;
// while(cr>='0'&&cr<='9')
// xr=(xr<<3)+(xr<<1)+(cr^48),cr=getchar();
// return xr*F;
//}
//void write(int x) //快写
//{
// if(x<0) putchar('-'),x=-x;
// if(x>9) write(x/10); putchar(x%10+'0');
//}
// 比 unordered_map 更快的哈希表
// #include <ext/pb_ds/assoc_container.hpp>
// using namespace __gnu_pbds;
// const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
// struct chash {
// int operator()(int x) const { return x ^ RANDOM; }
// };
// typedef gp_hash_table<int, int, chash> hash_t;
template<int P>
struct MInt {
int x;
constexpr MInt() : x{} {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return power(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt power(MInt a, ll b) {
MInt res = 1;
for (; b; b /= 2, a *= a) {
if (b % 2) {
res *= a;
}
}
return res;
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr std::istream &operator>>(std::istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr std::ostream &operator<<(std::ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
constexpr int P = 998244353; //这里为自动模数
using mint = MInt<P>; //mint是其定理的类型
string s,ss;
void icealsoheat(){
cin>>s>>ss;
if(s=="1"||ss=="1"){
if(s==ss)cout<<"0\n";
else{
cout<<"-1\n";
}
return;
}
if(s=="0"||ss=="0"){
if(s==ss)cout<<"0\n";
else cout<<"-1\n";
return ;
}
s=" "+s;
ss=" "+ss;
string now="";
int le=0;
vector<PII>ans;
int sum=0;
for(int i=1;i<s.size();i++){
if(s[i]=='0'&&le==0){
le=i;
}
else if(s[i]=='1'){
if(le!=0){
ans.push_back({le-sum,i-sum});
sum+=i-le;
}
le=0;
now+='1';
}
}
if(le!=0){
ans.push_back({le-sum,s.size()-1-sum});
now+='0';
le=1;
}
int sz=now.size();
now=" "+now;
cout<<now<<"\n";
for(int i=sz;i>1;i--){
if(now[i]=='1'&&now[i-1]=='1'){
ans.push_back({i-1,i});
// cout<<i<<" "<<i-1<<"++\n";
le+=2;
}
}
ans.push_back({2,2+le-1});
ans.push_back({1,2});
ans.push_back({1,2});
// int id=3;
for(int i=ss.size()-1;i>=2;i--){
if(i==2){
if(ss[i]=='1'){
ans.push_back({2,3});
ans.push_back({1,2});
}
else{
ans.push_back({2,3});
}
}
else if(ss[i]=='1'){
ans.push_back({1,2});
ans.push_back({2,3});
ans.push_back({1,2});
}
else{
ans.push_back({1,2});
ans.push_back({1,2});
}
}
cout<<ans.size()<<"\n";
for(auto [i,j]:ans){
cout<<i<<" "<<j<<"\n";
}
}
signed main(){
ios::sync_with_stdio(false); //int128不能用快读！！！！！！
cin.tie();
cout.tie();
int _yq;
_yq=1;
cin>>_yq;
while(_yq--){
icealsoheat();
}
}
//
//⠀⠀⠀ ⠀⢸⣿⣿⣿⠀⣼⣿⣿⣦⡀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠀⠀⠀ ⠀⢸⣿⣿⡟⢰⣿⣿⣿⠟⠁
//⠀⠀⠀⠀⠀⠀⠀⢰⣿⠿⢿⣦⣀⠀⠘⠛⠛⠃⠸⠿⠟⣫⣴⣶⣾⡆
//⠀⠀⠀⠀⠀⠀⠀⠸⣿⡀⠀⠉⢿⣦⡀⠀⠀⠀⠀⠀⠀ ⠛⠿⠿⣿⠃
//⠀⠀⠀⠀⠀⠀⠀⠀⠙⢿⣦⠀⠀⠹⣿⣶⡾⠛⠛⢷⣦⣄⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣿⣧⠀⠀⠈⠉⣀⡀⠀ ⠀⠙⢿⡇
//⠀⠀⠀⠀⠀⠀⢀⣠⣴⡿⠟⠋⠀⠀⢠⣾⠟⠃⠀⠀⠀⢸⣿⡆
//⠀⠀⠀⢀⣠⣶⡿⠛⠉⠀⠀⠀⠀⠀⣾⡇⠀⠀⠀⠀⠀⢸⣿⠇
//⢀⣠⣾⠿⠛⠁⠀⠀⠀⠀⠀⠀⠀⢀⣼⣧⣀⠀⠀⠀⢀⣼⠇
//⠈⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⢀⣴⡿⠋⠙⠛⠛⠛⠛⠛⠁
//⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣾⡿⠋⠀
//⠀⠀⠀⠀⠀⠀⠀⠀⢾⠿⠋⠀
//
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3840kb
input:
3 1 111 110110 1101010 1111 111111
output:
-1 11110 22 3 4 5 5 3 4 2 3 1 2 2 8 1 2 1 2 1 2 1 2 1 2 2 3 1 2 1 2 1 2 1 2 2 3 1 2 1 2 1 2 2 3 1 2 1111 20 3 4 2 3 1 2 2 7 1 2 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 1 2 2 3 1 2 2 3 1 2
result:
wrong answer Integer parameter [name=cnt] equals to 11110, violates the range [-1, 500] (test case 2)