Submission #238247

#	Time	Username	Problem	Language	Result	Execution time	Memory
238247		Dremix10	Lamps (JOI19_lamps)	C++17	6 / 100	1098 ms	3540 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
#define F first
#define S second
#define endl '\n'
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define maxp 22
#define EPS (ld)(1e-18)
#define mod (int)(1e9+7)
#define N (int)(1e5+1)

int fuse(string s){
    int i;
    int num=0;
    for(i=0;i<s.size();i++)
        if(s[i]=='1')
        num+=(1<<i);
    return num;
}

int main (){
fastio;

int n;
cin>>n;

string a,b;
cin>>a>>b;

int i,j,k;
queue <pair<int,int> > q;
q.push({fuse(a),0});
int want=fuse(b);

map<int,bool> v;

while(!q.empty()){
    int start=q.front().F;
    int cost=q.front().S;
    q.pop();

    if(v[start])
        continue;

    v[start]=1;

    if(start==want){
        cout<<cost<<endl;
        return 0;
    }
    cost++;

    int pos=0;
    while((start&(1<<pos))==(want&(1<<pos)))
        pos++;


    for(j=pos;j<n;j++){
        int num=0;
        for(k=0;k<n;k++)
            if(pos<=k && k<=j)
                num+=(1<<k);
            else if(start&(1<<k))
                num+=(1<<k);
        q.push({num,cost});
    }

    for(j=pos;j<n;j++){
        int num=0;
        for(k=0;k<n;k++)
            if(pos<=k && k<=j)
                num+=0;
            else if(start&(1<<k))
                num+=(1<<k);
        q.push({num,cost});
    }

    for(j=pos;j<n;j++){
        int num=0;
        for(k=0;k<n;k++)
            if(pos<=k && k<=j){
                if(!(start&(1<<k)))
                    num+=(1<<k);
            }
            else if(start&(1<<k))
                num+=(1<<k);
        q.push({num,cost});
    }


}



}

Compilation message (stderr)

lamp.cpp: In function 'int fuse(std::__cxx11::string)':
lamp.cpp:18:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<s.size();i++)
             ~^~~~~~~~~
lamp.cpp: In function 'int main()':
lamp.cpp:33:5: warning: unused variable 'i' [-Wunused-variable]
 int i,j,k;
     ^

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