oj.uz

Submission #1107720

# Submission time Handle Problem Language Result Execution time Memory
1107720 2024-11-02T03:51:14 Z 8pete8 Stray Cat (JOI20_stray) C++17
15 / 100
 42 ms 16736 KB 
#include "Anthony.h"
#include <vector>
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
using namespace std;
namespace {

int FunctionExample(int i, int A) {
  return i % A;
}

}  // namespace

vector<int> Mark(int n,int m, int a, int b,vector<int> U,vector<int> V) {
  vector<int> X(m);
  vector<int>lvl(n+1,1e9),vis(n,0);
  vector<vector<pii>>adj(n);
  for(int i=0;i<m;i++){
    adj[U[i]].pb({V[i],i}),adj[V[i]].pb({U[i],i});
  }
  queue<int>q;
  lvl[0]=0;
  q.push(0);
  while(!q.empty()){
    int cur=q.front();
    q.pop();
    if(vis[cur])continue;
    vis[cur]=1;
    for(auto i:adj[cur])if(!vis[i.f]&&lvl[i.f]>lvl[cur]+1){
      lvl[i.f]=lvl[cur]+1;
      q.push(i.f);
    }
  }
  if(a>=3){
    for(int i=0;i<n;i++)for(auto j:adj[i]){
      if(lvl[j.f]<lvl[i])X[j.s]=(lvl[j.f]%3);
      else X[j.s]=lvl[i]%3;
    }
  }
  else{
    //0 0 1 1 0 1
    //1 1 0 1 0 0
    vector<int>pat={0,0,1,1,0,1};
    vector<int>val(n,0);
    function<void(int,int,int)> dfs=[&](int cur,int p,int c){
      for(auto i:adj[cur])if(i.f!=p){
        if(adj[cur].size()>2){
          c=0;
          val[i.f]=val[cur]^1;
          X[i.s]=val[i.f];
          dfs(i.f,cur,c);
        }
        else{
          if(c==0){
            val[i.f]=val[cur]^1;
            if(val[i.f])c=2;
            if(cur)c++;
            X[i.s]=val[i.f];
            dfs(i.f,cur,c+1);
          }
          else{
            val[i.f]=pat[c%6];
            X[i.s]=val[i.f];
            dfs(i.f,cur,c+1);
          }
        }
        
      }
    };
    dfs(0,-1,0);
  }
  //for(int i=0;i<m;i++)cout<<U[i]<<" "<<V[i]<<" "<<X[i]<<'\n';
  return X;
}

#include "Catherine.h"
#include <vector>
#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<cassert>
#include<unordered_map>
#include <queue>
#include <cstdint>
#include<cstring>
#include<limits.h>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric>
#include<bitset>
using namespace std;
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
#pragma GCC optimize ("03,unroll-lopps")
using namespace std;
using namespace std;
namespace {

int a, b;
int variable_example = 0;
int found=0;
int add[40000];
deque<int>cor={1,0,1,1,0,0};
vector<int>have;
int st=0,last=0;
}
void Init(int A, int B){
  ::a = A;
  ::b = B;
  found=0;
  have.clear();
}
int Move(vector<int> y){
  int cnt=0;
  for(auto i:y)cnt+=!!i;
  if(a>=3){
    if(cnt==0)assert(0);
    if(cnt==1){
      for(int i=0;i<y.size();i++)if(y[i])return i;
    }
    if(cnt==2){
      if(y[0]&&y[2])return 2;
      if(y[1]&&y[2])return 1;
      if(y[0]&&y[1])return 0;
    }
    assert(0);
  }
  else{
    int one=0,two=0;
    if(st==0){
      for(int i=0;i<y.size();i++)if(y[i]==1)one++;
      if(one==1){
        st=1;
        found=1;
        for(int i=0;i<y.size();i++)if(y[i]==1)return last=i;
      }
      else{
        st=1;
        for(int i=0;i<y.size();i++)if(y[i]){
          have.pb(i);
          return last=i; 
        }
      }
      st=1;
    }
    if(!found){
      if(cnt==0){
        found=1;
        return -1;
      }
      for(int i=0;i<y.size();i++)if(y[i]>=2)two++;
      if(two){
        found=1;
        return -1;
      }
      if(have.size()<6){
        for(int i=0;i<y.size();i++)if(y[i]){
          have.pb(i);
          return last=i;
        }
      }
      else{
        int same=0;
        for(int i=0;i<6;i++){
          int yes=1;
          for(int j=0;j<6;j++)if(have[j]!=cor[j])yes=0;
          same|=yes;
          cor.push_back(cor.front());
          cor.pop_front();
        }
        found=1;
        if(!same)return -1;
      }
    }
    if(found){
      for(int i=0;i<y.size();i++)if(y[i]==1)one++;
      if(one==0)return -1;
      if(one==1){
        for(int i=0;i<y.size();i++)if(y[i])return last=i;
      }
      else{
        y[last]++;
        for(int i=0;i<y.size();i++)if(y[i]==1)return last=i;
      }
    }
  }
  assert(0);
  return -1;
}

Compilation message

Anthony.cpp:34:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Anthony.cpp:38:33: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   38 | int FunctionExample(int i, int A) {
      |                                 ^
Anthony.cpp:44:71: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   44 | vector<int> Mark(int n,int m, int a, int b,vector<int> U,vector<int> V) {
      |                                                                       ^
Anthony.cpp: In function 'std::vector<int> Mark(int, int, int, int, std::vector<int>, std::vector<int>)':
Anthony.cpp:75:60: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   75 |     function<void(int,int,int)> dfs=[&](int cur,int p,int c){
      |                                                            ^
Anthony.cpp: At global scope:
Anthony.cpp:38:5: warning: 'int {anonymous}::FunctionExample(int, int)' defined but not used [-Wunused-function]
   38 | int FunctionExample(int i, int A) {
      |     ^~~~~~~~~~~~~~~

Catherine.cpp:34:40: warning: bad option '-funroll-lopps' to pragma 'optimize' [-Wpragmas]
   34 | #pragma GCC optimize ("03,unroll-lopps")
      |                                        ^
Catherine.cpp:47:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   47 | void Init(int A, int B){
      |                       ^
Catherine.cpp:53:23: warning: bad option '-funroll-lopps' to attribute 'optimize' [-Wattributes]
   53 | int Move(vector<int> y){
      |                       ^
Catherine.cpp: In function 'int Move(std::vector<int>)':
Catherine.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |       for(int i=0;i<y.size();i++)if(y[i])return i;
      |                   ~^~~~~~~~~
Catherine.cpp:71:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |       for(int i=0;i<y.size();i++)if(y[i]==1)one++;
      |                   ~^~~~~~~~~
Catherine.cpp:75:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |         for(int i=0;i<y.size();i++)if(y[i]==1)return last=i;
      |                     ~^~~~~~~~~
Catherine.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |         for(int i=0;i<y.size();i++)if(y[i]){
      |                     ~^~~~~~~~~
Catherine.cpp:91:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |       for(int i=0;i<y.size();i++)if(y[i]>=2)two++;
      |                   ~^~~~~~~~~
Catherine.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |         for(int i=0;i<y.size();i++)if(y[i]){
      |                     ~^~~~~~~~~
Catherine.cpp:116:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  116 |       for(int i=0;i<y.size();i++)if(y[i]==1)one++;
      |                   ~^~~~~~~~~
Catherine.cpp:119:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |         for(int i=0;i<y.size();i++)if(y[i])return last=i;
      |                     ~^~~~~~~~~
Catherine.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |         for(int i=0;i<y.size();i++)if(y[i]==1)return last=i;
      |                     ~^~~~~~~~~
Catherine.cpp: At global scope:
Catherine.cpp:42:5: warning: '{anonymous}::add' defined but not used [-Wunused-variable]
   42 | int add[40000];
      |     ^~~
Catherine.cpp:40:5: warning: '{anonymous}::variable_example' defined but not used [-Wunused-variable]
   40 | int variable_example = 0;
      |     ^~~~~~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15364 KB Output is correct
2 Correct 1 ms 776 KB Output is correct
3 Correct 26 ms 14680 KB Output is correct
4 Correct 42 ms 16192 KB Output is correct
5 Correct 37 ms 16736 KB Output is correct
6 Correct 31 ms 15180 KB Output is correct
7 Correct 38 ms 15836 KB Output is correct
8 Correct 34 ms 16228 KB Output is correct
9 Correct 37 ms 15936 KB Output is correct

Subtask #2
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 15364 KB Output is correct
2 Correct 1 ms 776 KB Output is correct
3 Correct 26 ms 14680 KB Output is correct
4 Correct 42 ms 16192 KB Output is correct
5 Correct 37 ms 16736 KB Output is correct
6 Correct 31 ms 15180 KB Output is correct
7 Correct 38 ms 15836 KB Output is correct
8 Correct 34 ms 16228 KB Output is correct
9 Correct 37 ms 15936 KB Output is correct
10 Correct 26 ms 13268 KB Output is correct
11 Correct 27 ms 13428 KB Output is correct
12 Correct 28 ms 13216 KB Output is correct
13 Correct 37 ms 12996 KB Output is correct
14 Correct 33 ms 13824 KB Output is correct
15 Correct 31 ms 14308 KB Output is correct
16 Correct 35 ms 16220 KB Output is correct

Subtask #3
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12844 KB Output is correct
2 Correct 2 ms 780 KB Output is correct
3 Correct 31 ms 12352 KB Output is correct
4 Correct 36 ms 14700 KB Output is correct
5 Correct 37 ms 14856 KB Output is correct
6 Correct 27 ms 12868 KB Output is correct
7 Correct 32 ms 12896 KB Output is correct
8 Correct 39 ms 13916 KB Output is correct
9 Correct 34 ms 13868 KB Output is correct
10 Correct 32 ms 13696 KB Output is correct
11 Correct 33 ms 13616 KB Output is correct
12 Correct 33 ms 13632 KB Output is correct
13 Correct 32 ms 13664 KB Output is correct
14 Correct 37 ms 13848 KB Output is correct
15 Correct 32 ms 14016 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 12844 KB Output is correct
2 Correct 2 ms 780 KB Output is correct
3 Correct 31 ms 12352 KB Output is correct
4 Correct 36 ms 14700 KB Output is correct
5 Correct 37 ms 14856 KB Output is correct
6 Correct 27 ms 12868 KB Output is correct
7 Correct 32 ms 12896 KB Output is correct
8 Correct 39 ms 13916 KB Output is correct
9 Correct 34 ms 13868 KB Output is correct
10 Correct 32 ms 13696 KB Output is correct
11 Correct 33 ms 13616 KB Output is correct
12 Correct 33 ms 13632 KB Output is correct
13 Correct 32 ms 13664 KB Output is correct
14 Correct 37 ms 13848 KB Output is correct
15 Correct 32 ms 14016 KB Output is correct
16 Correct 31 ms 11752 KB Output is correct
17 Correct 25 ms 11220 KB Output is correct
18 Correct 26 ms 11736 KB Output is correct
19 Correct 26 ms 11564 KB Output is correct
20 Correct 28 ms 12136 KB Output is correct
21 Correct 27 ms 12080 KB Output is correct
22 Correct 31 ms 14056 KB Output is correct
23 Correct 32 ms 11716 KB Output is correct
24 Correct 27 ms 11752 KB Output is correct

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1024 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 71.0

# Verdict Execution time Memory Grader output
1 Incorrect 25 ms 11148 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 24 ms 11160 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -