oj.uz

Submission #426594

# Submission time Handle Problem Language Result Execution time Memory
426594 2021-06-14T07:25:15 Z 조영욱(#7645) Ancient Machine (JOI21_ancient_machine) C++17
5 / 100
 62 ms 5448 KB 
#include "Anna.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int variable_example = 0;

}

void Anna(int n,vector<char> s) {
    for(int i=0;i<n;i++) {
        int val=s[i]-'X';
        Send(val/2);
        Send(val%2);
    }
}

#include "Bruno.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

int dp[262144];
int pr[262144];
int arr[18];
int n;
int ans(int bit) {
    if (bit==0) {
        return 0;
    }
    if (dp[bit]!=-1) {
        return dp[bit];
    }
    int ret=0;
    for(int i=0;i<n;i++) {
        if (bit&(1<<i)) {
            if (arr[i]!=1) {
                if (ans(bit-(1<<i))>=ret) {
                    pr[bit]=i;
                }
                ret=max(ret,ans(bit-(1<<i)));
                continue;
            }
            bool flag1=false;
            bool flag2=false;
            for(int j=i-1;j>=0;j--) {
                if (bit&(1<<j)) {
                    if (arr[j]==0) {
                        flag1=true;
                    }
                    break;
                }
            }
            for(int j=i+1;j<n;j++) {
                if (bit&(1<<j)) {
                    if (arr[j]==2) {
                        flag2=true;
                    }
                    break;
                }
            }
            if (flag1&flag2){
                if (ans(bit-(1<<i))+1>=ret) {
                    pr[bit]=i;
                }
                ret=max(ret,ans(bit-(1<<i))+1);
            }
            else {
                if (ans(bit-(1<<i))>=ret) {
                    pr[bit]=i;
                }
                ret=max(ret,ans(bit-(1<<i)));
            }
        }
    }
    return dp[bit]=ret;
}
}  // namespace

void Bruno(int nn,int l,vector<int> v) {
    n=nn;
  for (int i = 0;i<l;i+=2) {
    arr[i/2]=v[i]*2+v[i+1];
  }
  memset(dp,-1,sizeof(dp));
  int now=(1<<n)-1;
  for(int i=0;i<n;i++) {
        ans(now);
    Remove(pr[now]);
    now-=(1<<pr[now]);
  }
}

Compilation message

Anna.cpp:7:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
    7 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 2540 KB Output is correct
2 Correct 51 ms 2532 KB Output is correct
3 Correct 54 ms 2536 KB Output is correct
4 Correct 56 ms 2532 KB Output is correct
5 Correct 54 ms 2532 KB Output is correct
6 Correct 51 ms 2532 KB Output is correct
7 Correct 2 ms 1508 KB Output is correct
8 Correct 2 ms 1508 KB Output is correct
9 Correct 54 ms 2540 KB Output is correct
10 Correct 62 ms 2532 KB Output is correct
11 Correct 53 ms 2536 KB Output is correct

Subtask #2
0 / 95.0

# Verdict Execution time Memory Grader output
1 Incorrect 52 ms 5448 KB Wrong Answer [4]
2 Halted 0 ms 0 KB -