General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
90664262 Practice:
RainAir
1392G - 25 GNU C++11 Accepted 389 ms 27672 KB 2020-08-22 10:16:00 2020-08-22 10:16:00
→ Source
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define db double
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;
int n,m,k;
char str[21];
int x[MAXN],y[MAXN];
int s[MAXN],t[MAXN];
int p[21];
int f[(1<<20)+3],g[(1<<20)+3];
// f 最小 g 最大

inline void presum(){
    FOR(i,0,k-1){
        FOR(S,0,(1<<k)-1){
            if((S>>i)&1) continue;
            f[S] = std::min(f[S^(1<<i)],f[S]);
            g[S] = std::max(g[S^(1<<i)],g[S]);
        }
    }
}

int main(){
    scanf("%d%d%d",&n,&m,&k);
    scanf("%s",str);FOR(i,0,k-1) if(str[i] == '1') s[0] |= (1<<i);
    scanf("%s",str);FOR(i,0,k-1) if(str[i] == '1') t[0] |= (1<<i);
    FOR(i,1,n) scanf("%d%d",x+i,y+i);FOR(i,1,k) p[i] = i;
    FOR(i,1,n){
        int p1=-1,p2=-1;
        FOR(j,1,k){
            if(p[j] == x[i]) p1 = j;
            if(p[j] == y[i]) p2 = j;
        }
        std::swap(p[p1],p[p2]);
//        FOR(i,1,k) printf("%d" ,p[i]);puts("");
        FOR(j,0,k-1) if((s[0]>>(p[j+1]-1))&1) s[i] |= 1<<j;
        FOR(j,0,k-1) if((t[0]>>(p[j+1]-1))&1) t[i] |= 1<<j;
//        FOR(j,0,k-1) printf("%d",(s[i]>>j)&1);puts("");
    }
    FOR(i,0,(1<<k)-1) f[i] = 1e9,g[i] = -1e9;
    FOR(i,0,n) f[s[i]] = std::min(f[s[i]],i),g[t[i]] = std::max(g[t[i]],i);
    presum();
    int ans = -1e9,ansl = -1,ansr = -1;
    FOR(S,0,(1<<k)-1){
        if(g[S]-f[S] >= m && __builtin_popcount(S) > ans){
            ans = __builtin_popcount(S);
            ansl = f[S]+1;ansr = g[S];
        }
    }
    ans = 2*ans+k-__builtin_popcount(s[0])-__builtin_popcount(t[0]);
    printf("%d\n%d %d\n",ans,ansl,ansr);
    return 0;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details