NC209996. GitMerge
描述
#include <bits/stdc++.h> int main() { <<<<<<< branch1 printf("Hello world!"); ======= puts("Hello World!"); >>>>>>> branch2 } Here's an example of merging Hello World. The one on branch1 used printf, but the second programmer prefered puts. Well, one solution of that problem is to make some proper defines and make things work when different preset is on. One of the simplest ways is to change the git's mark into define, that is,
#include <bits/stdc++.h> int main() { #ifdef branch1 printf("Hello world!"); #else puts("Hello World!"); #endif } However, sometimes git will not mark an accurate range for simplicity that replacing the marks will not result one shortest answer. The following code could be shorter if add defines differently.
#include <bits/stdc++.h> using namespace std; int main() { int a, b; <<<<<<< branch1 cin >> a >> b; ======= scanf("%d%d", &a, &b); >>>>>>> branch2 if (a < 0 || b < 0) return 1; <<<<<<< branch1 cout << a + b << endl; ======= printf("%d\n", a + b); >>>>>>> branch2 } Your task here is to output one of the shortest possible merge answers, for some C++ code. Here're some definitions and limitations:
* There will be 1 or more conflicts in the file. The conflicts are marked with exactly the same format with the sample code. That is,
* "<<<<<<< branch1" for the beginning.
* "=======" for separating conflicts.
* ">>>>>>> branch2" for ending.
* There're 0 or more lines of code between marks.
* No "<<<<<<< branch2" or ">>>>>>> branch1" will be presented in the code.
* No nesting conflicts will be presented in the code.
* No other lines start with "<<<<<<<", "=======" or ">>>>>>>".
* The input file may not necessarily be output of git, and there's no guarantee of niceness of the marks: it may contain 'surprising' output like later samples. However, it will strictly follow the format.
#ifdef branch1 #ifdef branch2 #else #endif
* You're not supposed to insert any other directives apart from the above ones or preprocess any directives in the code.
* There's no other #if #ifdef #ifndef #endif directives in the code and no #define #undef related to "branch1" "branch2", so you don't need to treat preprocessor directives different from normal code.
* The char set of input file is all visible ASCII chars (from 33 to 126), '\n', '\t', and space(32). The line break is granted to be '\n' but not "\r\n".
* 'Shortest' means the number of lines of the code is minimum. It's not necessarily to output a shortest answer in bytes.
输入描述
Input file consists of at most 4000 lines of code or git marks, with each line at most 256 byte including '\n'.It's granted that there's at least one conflict and at least one code line.
输出描述
The code with minimum number of lines that will be the exact match with two branches when different defines on. If there're multiple answers, print any.The checker will try to fix some unpleasant issues, including ignore spaces at end of line and extra line breaks at end of file. However, you're recommended to output your answer in the format of samples in order to avoid Wrong Answer caused by Presentation Error.The output must be shorter than 5000 lines with each line at most 300 byte including '\n'. Otherwise, you will receive Wrong Answer verdict.
示例1
输入:
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
<<<<<<< branch1
cin >> a >> b;
=======
scanf("%d%d", &a, &b);
>>>>>>> branch2
if (a < 0 || b < 0) return 1;
<<<<<<< branch1
cout << a + b << endl;
=======
printf("%d\n", a + b);a
>>>>>>> branch2
}
输出:
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
#ifdef branch1
cin >> a >> b;
if (a < 0 || b < 0) return 1;
cout << a + b << endl;
#else
scanf("%d%d", &a, &b);
if (a < 0 || b < 0) return 1;
printf("%d\n", a + b);a
#endif
}
示例2
输入:
<<<<<<< branch1
int main() {
return 0;
}
=======
int main() {
}
>>>>>>> branch2
输出:
int main() {
#ifdef branch1
return 0;
#endif
}
示例3
输入:
<<<<<<< branch1
int main() {}
=======
int main() {}
>>>>>>> branch2
输出:
int main() {}
C++14(g++5.4) 解法, 执行用时: 241ms, 内存消耗: 192396K, 提交时间: 2020-07-25 17:25:42
#include<bits/stdc++.h>
#define rep(i,x,y) for(auto i=(x);i<=(y);++i)
#define dep(i,x,y) for(auto i=(x);i>=(y);--i)
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
const int N=4010;
const ll mo=1e15+487;
const int inf=1e9;
int a[N][N],b[N],c[N],d[N];ll h1[N],h2[N];
pii f[N][N],bf[N],cf[N],df[N];string s1[N],s2[N];
ll ha(const string&s){
ll res=0;int sz=s.length();
for(ll i=0,p=1;i<sz;i++,p=p*131ll%mo)
res=(res+p*s[i])%mo;
return res;
}
void dfs(int x,int y){
if(!x&&!y)return;
int i=f[x][y].fr,j=f[x][y].sc;
if(i==-1&&j==-1){
dfs(x-1,y-1);puts(s1[x].c_str());
}else if(i==x){
dfs(i,j);puts("#ifdef branch2");
for(++j;j<=y;++j)puts(s2[j].c_str());
puts("#endif");
}else if(j==y){
dfs(i,j);puts("#ifdef branch1");
for(++i;i<=x;++i)puts(s1[i].c_str());
puts("#endif");
}else{
dfs(i,j);puts("#ifdef branch1");
for(++i;i<=x;++i)puts(s1[i].c_str());
puts("#else");
for(++j;j<=y;++j)puts(s2[j].c_str());
puts("#endif");
}
}
int main(){
string str;int n=0,m=0,fl=0;
while(getline(cin,str)){
if(str=="<<<<<<< branch1")fl=1;
else if(str=="=======")fl=2;
else if(str==">>>>>>> branch2")fl=0;
else{
if(fl!=2){
s1[++n]=str;
h1[n]=ha(str);
}
if(fl!=1){
s2[++m]=str;
h2[m]=ha(str);
}
}
}
rep(i,0,n)rep(j,0,m)a[i][j]=inf;
rep(i,0,n)b[i]=inf;
rep(i,0,m)c[i]=inf;
a[0][0]=0;b[0]=c[0]=d[0]=0;
rep(i,0,n)rep(j,0,m)if(i||j){
if(b[i]-i<d[j]){
d[j]=b[i]-i;
df[j]=bf[i];
}
if(i&&j&&h1[i]==h2[j]&&a[i-1][j-1]+1<a[i][j]){
a[i][j]=a[i-1][j-1]+1;
f[i][j]={-1,-1};
}
if(b[i]+2+j<a[i][j]){
a[i][j]=b[i]+2+j;
f[i][j]=bf[i];
}
if(c[j]+2+i<a[i][j]){
a[i][j]=c[j]+2+i;
f[i][j]=cf[j];
}
if(d[j]+3+i+j<a[i][j]){
a[i][j]=d[j]+3+i+j;
f[i][j]=df[j];
}
if(a[i][j]-j<b[i]){
b[i]=a[i][j]-j;
bf[i]={i,j};
}
if(a[i][j]-i<c[j]){
c[j]=a[i][j]-i;
cf[j]={i,j};
}
if(a[i][j]-i-j<d[j]){
d[j]=a[i][j]-i-j;
df[j]={i,j};
}
}
dfs(n,m);
}
C++11(clang++ 3.9) 解法, 执行用时: 207ms, 内存消耗: 193560K, 提交时间: 2020-09-02 19:07:43
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define maxn 4010
#define mod 998244353
int n=0,m=0;
string s[2][maxn];
int h[2][maxn];
int Hash(string c){
int re=0,len=c.length();
for(int i=0;i<len;i++)re=(37ll*re+c[i])%mod;
return re;
}
void input(){
string c;int type=0;
while(getline(cin,c)){
if(c=="<<<<<<< branch1")type=1;
else if(c=="=======")type=2;
else if(c==">>>>>>> branch2")type=0;
else{
if(type!=2)s[0][++n]+=c;
if(type!=1)s[1][++m]+=c;
}
}
for(int i=1;i<=n;i++)h[0][i]=Hash(s[0][i]);
for(int i=1;i<=m;i++)h[1][i]=Hash(s[1][i]);
}
short f[maxn][maxn][3],fa[maxn][maxn][3];
void dp(){
memset(f,63,sizeof(f));f[0][0][0]=0;
memset(fa,-1,sizeof(fa));
for(int i=0;i<=n;i++)
for(int j=0;j<=m;j++)
for(int k=0;k<=2;k++){
if(f[i][j][k]+1+(k!=1)<f[i+1][j][1]){
f[i+1][j][1]=f[i][j][k]+1+(k!=1);
fa[i+1][j][1]=k;
}
if(f[i][j][k]+1+(k!=2)<f[i][j+1][2]){
f[i][j+1][2]=f[i][j][k]+1+(k!=2);
fa[i][j+1][2]=k;
}
if(h[0][i+1]==h[1][j+1]&&f[i][j][k]+1+(k!=0)<f[i+1][j+1][0]){
f[i+1][j+1][0]=f[i][j][k]+1+(k!=0);
fa[i+1][j+1][0]=k;
}
}
}
vector<int>op;
void output(){
int x=n+1,y=m+1,z=0;
while(x||y){
if(z==-1)printf("wulala"),exit(-1);
short p=fa[x][y][z];
if(z==0)x--,y--;
if(z==1)x--;
if(z==2)y--;
z=p;op.push_back(z);
}
op.pop_back();
reverse(op.begin(),op.end());
for(int i:op){
if(i==0){
if(z!=0)cout<<"#endif"<<endl;
cout<<s[0][++x]<<endl;y++;
}
if(i==1){
if(z==0)cout<<"#ifdef branch1"<<endl;
if(z==2)cout<<"#else"<<endl;
cout<<s[0][++x]<<endl;
}
if(i==2){
if(z==0)cout<<"#ifdef branch2"<<endl;
if(z==1)cout<<"#else"<<endl;
cout<<s[1][++y]<<endl;
}
z=i;
}
if(z!=0)cout<<"#endif"<<endl;
}
int main()
{
input();
dp();
output();
}