Submission #110586

#	Time	Username	Problem	Language	Result	Execution time	Memory
110586		icandoit	Lamps (JOI19_lamps)	C++14	0 / 100	1075 ms	263168 KiB

lamp

#include<bits/stdc++.h> 
#define ll long long int
#define mp make_pair
using namespace std;
    string p1(string a,int p,int q){
    	string s=a;
         for(int i=p;i<=q;i++){
         	  s[i]='1';
         }
          return s;
    }
     string p2(string a,int p,int q){
     	 string s=a;
          for(int i=p;i<=q;i++){
         	  s[i]='0';
         } 
          return s;
     }
       string p3(string a,int p,int q){
               string s=a;
        for(int i=p;i<=q;i++){
         	   if(s[i]=='0') s[i]='1';
         	    else {
         	    	 s[i]='0';
         	    }
          }
            return s;
       }
  map<string,bool> vis;
int main(){
       int n;
       cin>>n;
        string a;
         string b;
         cin>>a>>b;
         queue<pair<string,int>> qu;
        qu.push({a,0});
        vis[a]=1;
         while(!qu.empty()){
            string u=qu.front().first;
              int ans=qu.front().second;
               //cout<<u<<" "<<vis[u]<<endl;
               qu.pop(); 
                //cout<<u<<" "<<ans<<endl;
               
             if(u==b){
             	cout<<ans<<endl;
             	return 0;
             }

               for(int p=0;p<n;p++){
               	  for(int q=p;q<n;q++){
               	  	 string s1=p1(u,p,q);
               	  	  string s2=p2(u,p,q);
               	  	   string s3=p3(u,p,q);
               	  	  if(!vis[s1]){
               	  	   qu.push(mp(s1,ans+1));
                        vis[s1]=1;
               	  	}
               	  	    if(!vis[s2]){
               	  	   qu.push(mp(s2,ans+1));
                        vis[s2]=1;
               	  	}
               	  	  if(!vis[s3]){
               	  	   qu.push(mp(s3,ans+1));
                        vis[s3]=1;
               	  	}
               	  }
               }

         }

	return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49