제출 #897778

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
897778		AdamGS	Ancient Machine 2 (JOI23_ancient2)	C++17	98 / 100	38 ms	1104 KiB

ancient2

#include "ancient2.h"
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
bitset<1001>B[1000];
bool dodaj(bitset<1001>T) {
  rep(i, 1000) if(T[i]) {
    if(!B[i][i]) {
      B[i]=T;
      return true;
    }
    T^=B[i];
  }
  return false;
}
char znajdz(int x) {
  bitset<1001>T;
  T[x]=1;
  rep(i, 1000) if(T[i]) T^=B[i];
  return T[1000]+'0';
}
string Solve(int n) {
  vector<pair<int,int>>baza;
  int ile=0;
  rep(i, 100) {
    bitset<1001>T;
    T[i]=1;
    if(dodaj(T)) ++ile;
  }
  for(int i=1; ile<1000; ++i) {
    rep(j, i) {
      bitset<1001>T;
      for(int p=j; p<1000; p+=i) T[p]=1;
      if(dodaj(T)) {
        baza.pb({i, j});
        ++ile;
      }
    }
  }
  rep(i, 1000) rep(j, 1001) B[i][j]=0;
  rep(i, 100) {
    vector<int>a(i+3), b(i+3);
    rep(j, i) a[j]=b[j]=j+1;
    a[i]=i+1;
    b[i]=i+2;
    a[i+1]=b[i+1]=i+1;
    a[i+2]=b[i+2]=i+2;
    bitset<1001>T;
    T[i]=1;
    if(Query(i+3, a, b)==i+2) T[1000]=1;
    dodaj(T);
  }
  for(auto i : baza) {
    vector<int>a(2*i.st), b(2*i.st);
    rep(j, i.st) {
      a[j]=b[j]=(j+1)%i.st;
      a[j+i.st]=b[j+i.st]=(j+1)%i.st+i.st;
      if(j==i.nd) {
        b[j]+=i.st;
        b[j+i.st]-=i.st;
      }
    }
    bitset<1001>T;
    for(int p=i.nd; p<1000; p+=i.st) T[p]=1;
    if(Query(2*i.st, a, b)>=i.st) T[1000]=1;
    dodaj(T);
  }
  string ans="";
  rep(i, 1000) ans+=znajdz(i);
  return ans;
}

• Subtask 1: 98 / 100