oj.uz

Submission #110586

# Submission time Handle Problem Language Result Execution time Memory
110586 2019-05-11T09:03:56 Z icandoit Lamps (JOI19_lamps) C++14
0 / 100
 1000 ms 263168 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Execution timed out 1075 ms 7928 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Execution timed out 1075 ms 7928 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 75 ms 7296 KB Output is correct
8 Runtime error 480 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Execution timed out 1075 ms 7928 KB Time limit exceeded
9 Halted 0 ms 0 KB -