UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#215122#2656. adderican100817ms17588kbC++112.5kb2024-11-26 19:36:292024-11-26 23:02:18

answer

/*  Erica N  */
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define ull unsigned long long
#define pii pair<int, int>
#define ps second
#define pf first
#define itn int
#define rd read()
int read(){
    int xx = 0, ff = 1;char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-')ff = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9')xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
//       oid write(int out) {
// 	if (out < 0)
// 		putchar('-'), out = -out;
// 	if (out > 9)
// 		write(out / 10);
// 	putchar(out % 10 + '0');
// }
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }


const int N = 1e6 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 520040527;
const ull P=10;

string s;
int n;
int pw[N],hs[N];

inline pii min(pii a,pii b){
    return a<b?a:b;
}

pii ans={INF,INF};



inline int getHs(int l,int r){
    return (hs[r]-hs[l-1]*pw[r-l+1]%MOD+MOD)%MOD;
}

bool check(int a,int b){
    if(a<=0||a>=b)return 0;
    // if()return 0;
    if(s[a+1]=='0'&&b-a>1)return 0;
    if(s[b+1]=='0'&&n-b>1)return 0;

    int ha=getHs(1,a);
    int hb=getHs(a+1,b);
    int hc=getHs(b+1,n);

    // cdbg("ck",a,b,ha,hb,hc);
    if((ha+hb)%MOD==hc%MOD)return 1;
    return 0;

}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);


    cin>>s;
    n=s.size();
    s=" "+s;

    pw[0]=1;
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1]*P%MOD;
    }
    for(int i=1;i<=n;i++){
        hs[i]=(hs[i-1]*P%MOD+(s[i]-'0'))%MOD;
    }


    for(int i=n/2;i<=n-n/3+1;i++){
        //枚举=位置(i后面)
        int len=n-i;
        if(check(len,i))ans=min(ans,mp(len,i));
        if(check(len-1,i))ans=min(ans,mp(len-1,i));
        if(check(len+1,i))ans=min(ans,mp(len+1,i));
        if(check(i-len,i))ans=min(ans,mp(i-len,i));
        if(check(i-len-1,i))ans=min(ans,mp(i-len-1,i));
        if(check(i-len+1,i))ans=min(ans,mp(i-len+1,i));
    }

    // cdbg(ans.pf,ans.ps);
    if(ans.pf==INF)assert(0);

    for(int i=1;i<=n;i++){
        putchar(s[i]);
        if(i==ans.pf)putchar('+');
        if(i==ans.ps)putchar('=');
    }

    


}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 0ms
memory: 1212kb

input:

93944386991110939443869921

output:

939443869911+10=939443869921

result:

ok single line: '939443869911+10=939443869921'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1208kb

input:

454431423351945476661

output:

45443142+33519=45476661

result:

ok single line: '45443142+33519=45476661'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1212kb

input:

807674775734008076747757340

output:

8076747757340+0=8076747757340

result:

ok single line: '8076747757340+0=8076747757340'

Test #4:

score: 5
Accepted
time: 0ms
memory: 1208kb

input:

47936157175791479437362

output:

479361571+75791=479437362

result:

ok single line: '479361571+75791=479437362'

Test #5:

score: 5
Accepted
time: 0ms
memory: 1208kb

input:

8684160719450790868416071945079

output:

868416071945079+0=868416071945079

result:

ok single line: '868416071945079+0=868416071945079'

Test #6:

score: 5
Accepted
time: 0ms
memory: 1212kb

input:

3150325920082064131504079841

output:

31503259200+820641=31504079841

result:

ok single line: '31503259200+820641=31504079841'

Test #7:

score: 5
Accepted
time: 58ms
memory: 14780kb

input:

9261598869160335057970310229283612818845075445997339978957735823966059362624832990688056822195031820...

output:

9261598869160335057970310229283612818845075445997339978957735823966059362624832990688056822195031820...

result:

ok single line: '926159886916033505797031022928...3054231497478113058482456217163'

Test #8:

score: 5
Accepted
time: 62ms
memory: 15068kb

input:

4701609646464966471786112512122938863110668626139644802941307402470417596440427343650542031038908331...

output:

4701609646464966471786112512122938863110668626139644802941307402470417596440427343650542031038908331...

result:

ok single line: '470160964646496647178611251212...8748395060129898210762369495747'

Test #9:

score: 5
Accepted
time: 71ms
memory: 17588kb

input:

9257202799561473086244723527541134302291247300137775651258683390946286052100443441136004200934466749...

output:

9257202799561473086244723527541134302291247300137775651258683390946286052100443441136004200934466749...

result:

ok single line: '925720279956147308624472352754...2243909924739032590362234901192'

Test #10:

score: 5
Accepted
time: 62ms
memory: 16184kb

input:

4416728326936622856150699213135191910979789931946758505266833530473668185681946524100519868737557117...

output:

4416728326936622856150699213135191910979789931946758505266833530473668185681946524100519868737557117...

result:

ok single line: '441672832693662285615069921313...3111611421682233543698480114264'

Test #11:

score: 5
Accepted
time: 62ms
memory: 17300kb

input:

3061041362133228009344583160193669358685821190644364754039063887060686947993153784177860432362852231...

output:

3061041362133228009344583160193669358685821190644364754039063887060686947993153784177860432362852231...

result:

ok single line: '306104136213322800934458316019...4042293112332153562949434601781'

Test #12:

score: 5
Accepted
time: 75ms
memory: 17304kb

input:

8531603642906385747583399978283975747482545589702570907905311483331351132043885935451850547243462360...

output:

8531603642906385747583399978283975747482545589702570907905311483331351132043885935451850547243462360...

result:

ok single line: '853160364290638574758339997828...5180929300855954383525415798317'

Test #13:

score: 5
Accepted
time: 65ms
memory: 17316kb

input:

3334731073815946487356418721839719459473953466541212185094515699104064312397044785650155583747481091...

output:

3334731073815946487356418721839719459473953466541212185094515699104064312397044785650155583747481091...

result:

ok single line: '333473107381594648735641872183...2104466046161989376727619609117'

Test #14:

score: 5
Accepted
time: 57ms
memory: 16752kb

input:

7113181137342253409543193679407457232222929505170124047879622285985297849800487899060254257891240998...

output:

7113181137342253409543193679407457232222929505170124047879622285985297849800487899060254257891240998...

result:

ok single line: '711318113734225340954319367940...7499580501189814539270742795615'

Test #15:

score: 5
Accepted
time: 65ms
memory: 17300kb

input:

2226576415518523623432262365703901892218433052474981493103118406267304359951441730045611163295598279...

output:

2226576415518523623432262365703901892218433052474981493103118406267304359951441730045611163295598279...

result:

ok single line: '222657641551852362343226236570...1283546754745341452795514550351'

Test #16:

score: 5
Accepted
time: 64ms
memory: 17024kb

input:

7282380568017210841065149843225478309106222219195648724985194189592224139941051182898879219925651713...

output:

7282380568017210841065149843225478309106222219195648724985194189592224139941051182898879219925651713...

result:

ok single line: '728238056801721084106514984322...6665028468440209585025731431738'

Test #17:

score: 5
Accepted
time: 72ms
memory: 17588kb

input:

6172023021615818261278406139291452768117320772111777913293782100858187571870407831738505138788606992...

output:

6172023021615818261278406139291452768117320772111777913293782100858187571870407831738505138788606992...

result:

ok single line: '617202302161581826127840613929...9022854228506784321805225740782'

Test #18:

score: 5
Accepted
time: 41ms
memory: 11132kb

input:

1641729471229192950020661455158841378773007409709289573050186474289570718374236969060246403530844480...

output:

1641729471229192950020661455158841378773007409709289573050186474289570718374236969060246403530844480...

result:

ok single line: '164172947122919295002066145515...1428289195899821981683641721297'

Test #19:

score: 5
Accepted
time: 29ms
memory: 8056kb

input:

6878197288916471551222877849454599200431985721720556540869310866854759368074574456390764568703818252...

output:

6878197288916471551222877849454599200431985721720556540869310866854759368074574456390764568703818252...

result:

ok single line: '687819728891647155122287784945...4028111836067678989020741708082'

Test #20:

score: 5
Accepted
time: 34ms
memory: 9452kb

input:

1336335135465815186373041570173603326293570642638147764739718555949768772153761126675803325646928488...

output:

1336335135465815186373041570173603326293570642638147764739718555949768772153761126675803325646928488...

result:

ok single line: '133633513546581518637304157017...5916651705852916207264857823016'