제출 #1028542

#제출 시각아이디문제언어결과실행 시간메모리
1028542pcc저울 (IOI15_scales)C++17
0 / 100
1091 ms48232 KiB
#include "scales.h" #include <bits/stdc++.h> using namespace std; #define tiii tuple<int,int,int> #define pii pair<int,int> #define fs first #define sc second const int mxn = 1e6+10; const int N = 6; int tp[mxn]; vector<pii> tree[mxn]; int pw[N+1]; int ep = 0; const int lim = 10000; int encode(vector<int> v){ assert(v.size() == N); int re = 0; for(int i = 0;i<v.size();i++){ re += v[i]*pw[i]; } return re; } vector<int> decode(int k){ vector<int> re(N); for(int i = 0;i<N;i++){ re[i] = k%N; k/=N; } return re; } namespace TREE{ vector<int> cases; vector<int> param[mxn]; vector<int> op; bitset<mxn> done; void init(){ int pt = 0; for(int i = 0;i<N;i++){ for(int j = i+1;j<=N;j++){ for(int k = j+1;k<=N;k++){ param[pt] = {i,j,k,1}; op.push_back(pt); pt++; param[pt] = {i,j,k,2}; op.push_back(pt); pt++; param[pt] = {i,j,k,3}; op.push_back(pt); pt++; for(int l = 0;l<N;l++){ if(l == i||l == j||l == k)continue; param[pt] = {i,j,k,l,4}; op.push_back(pt); pt++; } } } } //cerr<<"OPS: "<<op.size()<<endl; vector<int> perm(N);for(int i = 0;i<N;i++)perm[i] = i; do{ cases.push_back(encode(perm)); }while(next_permutation(perm.begin(),perm.end())); //cerr<<"CASES: "<<cases.size()<<endl; return; } int f(int opid,int val){ auto v = param[opid]; auto arr = decode(val); sort(v.begin(),v.begin()+3,[&](int a,int b){return arr[a]<arr[b];}); if(v.back() == 1)return v[2]; else if(v.back() == 2)return v[0]; else if(v.back() == 3)return v[1]; else{ for(int i = 0;i<3;i++)if(arr[v[i]]>arr[v[3]])return v[i]; return v[0]; } } vector<pair<int,vector<int>>> part(int opid,vector<int> &v){ vector<pair<int,vector<int>>> re; for(int i = 0;i<v.size();i++){ int val = f(opid,v[i]); bool gp = false; for(auto &j:re){ if(j.fs == val)gp = true,j.sc.push_back(v[i]); } if(!gp)re.push_back(make_pair(val,vector<int>(1,v[i]))); } return re; } int vcnt = 0; int newnode(){ tree[vcnt].clear(); return vcnt++; } bool dfs(vector<int> &v,int dep,int nodeid){//false if fails if(v.size() == 1){ tp[nodeid] = v[0]; return true; } if(dep>=8)return false; ep++; //if(ep%lim == 0)cout<<ep<<" tries"<<','<<nodeid<<endl; //cerr<<nodeid<<":"<<dep<<','<<v.size()<<endl; for(auto &opid:op){ if(done[opid])continue; auto arr = part(opid,v); int sum = 0; bool flag = true; for(auto &i:arr)sum += i.sc.size(); for(auto &i:arr){ //if(sum>10&&sum-i.sc.size()<=5)flag = false; if(sum == i.sc.size())flag = false; } if(!flag)continue; done[opid] = true; tp[nodeid] = opid; for(auto &i:arr){ tree[nodeid].push_back(pii(i.fs,newnode())); flag = flag&&dfs(i.sc,dep+1,tree[nodeid].back().sc); if(!flag)break; } done[opid] = false; if(flag)return true; tp[nodeid] = -1; } while(vcnt>nodeid){ vcnt--; tree[vcnt].clear(); } vcnt = nodeid; return false; } void GO(){ init(); dfs(cases,0,newnode()); //cerr<<"TREE DONE!: "<<vcnt<<endl; for(int i = 0;i<vcnt;i++)cout<<tp[i]<<' ';cout<<endl; cout<<"EDGES: "<<endl; for(int i = 0;i<vcnt;i++){ for(auto nxt:tree[i])cout<<i<<' '<<nxt.fs<<' '<<nxt.sc<<endl; if(tree[i].empty()){ auto arr = decode(tp[i]); //cerr<<i<<": ";for(auto &i:arr)cerr<<i<<' ';cerr<<endl; } } return; } } void init(int T) { pw[0] = 1; for(int i = 1;i<=N;i++)pw[i] = pw[i-1]*N; TREE::GO(); } void orderCoins() { /* ... */ int ans[N] = {}; answer(ans); return; }

컴파일 시 표준 에러 (stderr) 메시지

scales.cpp: In function 'int encode(std::vector<int>)':
scales.cpp:21:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |  for(int i = 0;i<v.size();i++){
      |                ~^~~~~~~~~
scales.cpp: In function 'std::vector<std::pair<int, std::vector<int> > > TREE::part(int, std::vector<int>&)':
scales.cpp:85:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |   for(int i = 0;i<v.size();i++){
      |                 ~^~~~~~~~~
scales.cpp: In function 'bool TREE::dfs(std::vector<int>&, int, int)':
scales.cpp:114:37: warning: conversion from 'std::vector<int>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
  114 |    for(auto &i:arr)sum += i.sc.size();
      |                                     ^
scales.cpp:117:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |     if(sum == i.sc.size())flag = false;
      |        ~~~~^~~~~~~~~~~~~~
scales.cpp: In function 'void TREE::GO()':
scales.cpp:142:3: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  142 |   for(int i = 0;i<vcnt;i++)cout<<tp[i]<<' ';cout<<endl;
      |   ^~~
scales.cpp:142:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  142 |   for(int i = 0;i<vcnt;i++)cout<<tp[i]<<' ';cout<<endl;
      |                                             ^~~~
scales.cpp: In function 'void init(int)':
scales.cpp:155:15: warning: unused parameter 'T' [-Wunused-parameter]
  155 | void init(int T) {
      |           ~~~~^
#Verdict Execution timeMemoryGrader output
Fetching results...